首页天道酬勤kmp算法模式串next值(bf算法匹配字符串)

kmp算法模式串next值(bf算法匹配字符串)

admin 12-02 16:33 237次浏览

点击上面的‘java全栈技术’关注,每天学习一个Java知识点。

原文:仓明

KMP算法是一种高效的字符串匹配算法,由Knuth、Morris和Pratt提出,并以这三个名字的首字母来命名。在KMP之前,字符串匹配算法总是遍历字符串的每个字符进行比较,算法的复杂度为O(mn)。而KMP算法通过预处理可以将复杂度降低到0(m ^ n)。

knuth morris pratt算法

给定一个字符串1abcabcadef,我们现在需要搜索字符串2abcad在字符串1中的位置。对齐从位置0开始,到达位置5时发现字符不一样,字符串1的字符是C,字符串2的字符是d,接下来如何继续比较?这是KMP算法的核心。考虑到字符串2中有两个AB重复,我们可以将第一个AB移到第二个AB继续比较。在这个移动过程中,使用匹配的字符信息,字符串直接向前移动3位,以提高比较效率。

给定长度为n的字符串o,找到长度为m的字符串f出现在o中的位置,如下图所示(图片来自网络)。

当第I个字符不相等时,有必要向前移动字符串F以继续比较。KMP算法通过计算最大公共长度来移动。当满足以下条件时,f可以向前移动k位以继续对齐。

字符串是F的前缀;b是F的后缀;字符串a和字符串b相等。KMP算法的核心是求解f中每个位置之前字符串的前缀和后缀的最大公共长度,注意这个最大长度不包括字符串本身。当与第I个位置比较时,如果它们不相同,此时的最大公共长度为j,那么f的前向距离为k=Ij。

最大公共长度的计算

前缀是除最后一个字符以外的子字符串,后缀是除第一个字符以外的子字符串。对于字符串ABCA,前缀是A、AB和ABC,后缀是A、CA和BCA。相同前缀后缀只有a,最大公共长度是指当前位置前面字符串相同前缀后缀的最大长度,用下一个数组表示。根据此规则,上一个字符串2abcad的下一个数组如下表所示。对于长度为m的字符串,下一个数组的长度为m 1。显然,next[0]=next[1]=0。

已知A3=A0,next[4]=1。计算next[5]时,我们只需要比较B4=B1,然后A3B4=A0B1,next[5]=next[4] 1=2。

已知A3B4=A0B1,next[5]=2。下一步计算[6]时,先比较D5 C2,再比较A3B4D5 A0B1C2。如果有一个以B结尾的普通前缀,那么这个前缀一定在C2前面,这个前缀的长度是next[next[5]]=0,所以C2前面没有这样的前缀,D5不等于A0,next[6]=0。

假设我们得到了下一个[1],下一个[2],下一个[我]现在,我们需要下一个[我1]。可以看出,如果位置I和位置next[i]的两个字符相同,那么next[I 1]=next[I]1;如果两个位置的字符不相同,可以继续向前搜索,获取其最大公共长度next[next[i]],然后与位置I的字符进行比较,直到可以确定最终结果。(图片来自网络)

根据上面的分析,编写如下求解下一个数组的代码并不难。

串匹配

字符串匹配的过程类似于求解下一个数组的过程。我们假设搜索字符串F出现在字符串O中,F的索引是J,O的索引是I,如果O(i)=f(j),那么J=J ^ 1,继续比较F中的下一个字符;如果O(i) f(j),那么j=next[j],继续比较f中的字符和next[j]的位置,这相当于f向前移动了i-j位。当f的下标j移动到最后,表示匹配成功。此时可以计算出第一次出现的位置是I-J。

如下图所示,假设O为ABCABCABDEF,F为ABCABD。O(4)=f(4),然后继续比较O(5)和f(5)。O(5) f(5),那么F的下一个对齐字符位置是next[5]=2,继续O(5)和f(2)的下一个对齐,相当于F向前移动5-2=3位。当比较O(8)=f(5)时,F已经被比较到底,匹配成功。此时,O中的位置计算为8-5=3。

根据上面的分析,编写如下匹配字符串的代码并不难。

node.js环境变量指的是什么短信群发平台怎么正确做到的短信群发呢?Sessionjava包装类
量化投资用什么算法(学生违反课堂量化处理意见) java线程wait(线程的notify方法)
相关内容