kmp算法

问题：

判断一个串t是否为另一串s的子串，及t在s的位置如：t=”abab” , s=”abacabab”。

1、Brute-Force算法图解

时间复杂度O(strlen(t)*strlen(s))，效率低，在较大的数据下容易超时。

2、kmp算法匹配图解：

 

时间复杂度O(strlen(t)+strlen(s))，相对于Brute-Force算法效率高，避免了不必要的匹配，数据越大越明显。

算法：

1. 当前位置匹配成功，两个串的下标位置同时后移一位继续匹配
2. 当前位置匹配失败，根据next[]寻找下一个匹配位置

求next数组：

1. 寻找模式串t的最长前缀后缀最长公共元素长度

1. 获取next数组

next数组是考虑除去当前字符外的最长相同前缀后缀，即最长共元素长度表整体后移一位，初始值next[0]=-1;

通过前缀后缀最长公共元素长度求next数组：

int f[MAXN],next[MAXN];
void get_next(string t)
{
	int k=0;
	f[0]=0;
	for(int i=1;i<t.length();i++)//从第二个字符开始，依次计算每一个字符对应最长公共元素长度 
	{
		while(k&&t[k]!=t[i])//递归求最大的相同的前后缀长度k 
			k=f[k-1];
		if(t[k]==t[i])//如果相同这长度k+1 
			k++;
		f[i]=k;
	}
	next[0]=-1;
	for(int i=1;i<t.length();i++)//最长共元素长度表整体后移一位得到next数组 
		next[i]=f[i-1];
}

通过递推求next数组：

int next[MAXN];
void get_next(string t)
{
	next[0]=-1;
	int j=-1,i=0;
	while(i<t.length())
	{
		if(j==-1||t[j]==t[i])//前面部分相等时
			next[++i]=++j;
		else
			j=next[j];//不等时，j退到满足t0t1…tk-1”=” tj-Ktj-(k-1)…tj-1”的k处，即next[j]

	}
}

根据next数组匹配：

如果j==-1，或者当前位置字符匹配成功（s[i]==t[j]），则i++，j++

如果j!=-1,且当前位置字符匹配失败（s[i]!=t[j]），则j=next[j]，i位置不变。相当与t相对于s右移j-next[j];

当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next值

int next[MAXN];
void get_next(string t)
{
	next[0]=-1;
	int j=-1,i=0;
	while(i<t.length())
	{
		if(j==-1||t[j]==t[i])
			next[++i]=++j;
		else
			j=next[j];
	}
}
bool Kmp(string s,string t)
{
	get_next(t);
	int i=0,j=0;
	while(i<s.length())
	{
		if(j==-1||s[i]==t[j])
			j++,i++;
		else
			j=next[j];
		if(j>=t.length())
			return true;
	}
	return false;
}