KMP

在字符串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]吧,哈哈哈。想明白了就行了。

上一篇:String与常量池


下一篇:Golang入门到项目实战 | golang切片的初始化