首页 > 搜索 > 字符匹配算法比如,字符串匹配算法

字符匹配算法比如,字符串匹配算法

互联网 2020-10-25 19:11:51
在线算命,八字测算命理

以下为学习 《数据结构与算法之美 -- 字符串匹配》 的记录。

BF算法

即暴力匹配算法,循环遍历匹配。

RK算法

即根据哈希值进行匹配。假设主串长度为 m ,模式串长度为 n ,则只需计算主串中 m-n+1 个子串的哈希值,然后与模式串的哈希值相比即可。

哈希算法可以自定义。

比如使用字符集的个数作为几进制,然后将其转换成整数。

如果字符中只包含 a-z, 那么字符集的个数为 26 。则转换成 26 进制。

"aab" => ('a' - 'a') * 26 * 26 + ('a' - 'a') * 26 + ('b' - 'a') * 1

当有哈希冲突时,即当遇到不同的子串有相同哈希值时,再次与模式串的字符逐个比较是否相等。

BM算法

从后向前匹配,效率比经典的 KMP 算法还要快 3~4 倍。

坏字符规则

当遇到不匹配的字符(称之为坏字符),在模式串中的下标为 si 。

如果模式串中该字符不存在,则直接向后移动一个模式串的长度。如果存在,下标为 xi , 则移动 (si-xi) 位,使其跟主串的坏字符对应。

移动后,继续从模式串末尾开始匹配。

记录模式串中每个字符对应的 index ,重复的会被靠后的位置替代。

好后缀规则

当遇到不匹配的字符,将已经匹配过的字符(称之为好后缀)。

在模式串中查找是否能匹配整个好后缀,如有,则移动至对齐。若没有,则在模式串中查找是否有前缀子串跟好后缀的后缀子串匹配,若有,则移动最长的前缀子串与其对应。若没有,则直接移动整个模式串。后缀子串,最后一个字符跟其对齐,不包括首字符。abc,后缀子串为c,bc。前缀子串,第一个字符跟其对齐,不包括末尾。abc,前缀子串为a,ab。求好后缀的匹配串的位置

记录 suffix[k] = i ,k 表示后缀长度。subffix[1] = 1,表示最后一个字符在i=1开始是匹配的。如果不存在,则 suffix[k] = -1 。

比如字符串 "dacda", suffix 数组如下。

suffix[1] = 1suffix[2] = 0suffix[3] = -1suffix[4] = -1

由于还需要判断是否有前缀子串与后缀的后缀子串匹配,所以还需记录是否有前缀子串,prefix[k] = 0,表示末尾 k 位数,有匹配的前缀子串。若为 -1 ,则没有。

根据 suffix 数组,如果其值为 0,则表示有前缀子串。

prefix[1] = falseprefix[2] = trueprefix[3] = falseprefix[4] = false

suffix 数组计算方法:

模式串中的 0-i(0 Int {// 坏字符后面一个j+1,后缀长度为m-()let k = m - 1 - jif suffix[k] != -1 {return j + 1 - suffix[k]}// 遍历所有后缀子串var r = m + 2while r0 {i = lk = l} else {next[j] = 0j += 1}}}

代码:

// m-主串长度,n-模式串长度var i = 0var j = 0while i < m {if s[i] == pattern[j] {j += 1i += 1// 匹配完成if j == n {return i - j}} else {if i < m {if j >= 1 {j = next[j - 1]} else {i += 1}}}}return -1
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多