在字符串s1(长为n)中匹配字符串s2(长为m)
在不了解KMP的时候通常采用暴力法求解,即从s1开始往后逐个比较字符,如果匹配失败则s1的标记点加一,再从s2开始逐个比较
这样的话时间复杂度就为O(m*n)。(我之前都是用这种方式,虽然时间长但是能求出来)。
了解KMP之前先了解一下 “最长公共前后缀” 比如说一个字符串 s2=“abcdabc”则最长公共前后缀为 abc
例如 s1=“abcabcabcabcabcabb” s2=“abcabb” 匹配时
a b c a b cabcabcabcabb
a b c a b b
如上所示当第一次匹配失败时,按照暴力思维就是将s1标签后移一位即s1[1]与s2[0]进行比较,以此类推。
而当s1[5]与s2[5]不匹配时,在s1与s2已经匹配的公共字符串(上面的 abcab )里面找最长公共前后缀即 ab
然后回溯s2到最长公共前缀的后一个字符与s1当前字符比较如下
a b cabcabcabcabb
a b cabb
接着继续进行比较
a b c a b cabcabcabb
a b c a b b
当比较到s2的最后一位时匹配失败,再回溯s2
a b cabcabcabb
a b cabb
再接着继续进行比较
a b c a b cabcabb
a b c a b b
失败后再回溯
a b cabcabb
a b cabb
再往后比较
a b c a b cabb
a b c a b b
失败再回溯
a b cabb
a b cabb
匹配成功
a b c a b b
a b c a b b
好了,上面就是KMP的思想了,接下来我们解决如何求回溯到哪的问题,回溯到哪就是检查已经匹配的字符中的最大公共前后缀,然后回溯到前缀的后一个字符。
为了方便我们先开一个next数组用来存放s2的最大公共前后缀。
void funnext(string s,vector<int> & next)
{
int j,k;
j=0;k=-1;
next.push_back(-1);
while(j<s.length()-1)
{
if(k==-1||s[j]==s[k])
next[++j]=++k;
else
k=next[k];
}
}
接下来就是KMP了
int KMP(string s1,string s2,vector<int> next)
{
int j,k;
j=k=0;
while(j!=s1.length()&&k!=s2.length())
{
if(k==-1 || s1[j]==s2[k])
{
j++;
k++;
}
else{
k=next[k];
}
}
if(k==s2.length()){
return j-k;}
else
return -1;
}
时间复杂度由 O(m*n) 降到了O(m+n),空间复杂度变成了O(m)
当然了,还可以继续优化,这里就不进一步介绍了。
主要难理解的还是k=next[k]吧,哈哈哈。想明白了就行了。