KMP算法

KMP算法是一种字符串模式匹配算法。
什么是字符串的模式匹配？
给定两个串S=“s₁s₂s₃ …s_m”和T=“t₁t₂t₃ …t_n”，在主串S中寻找子串T的过程叫做模式匹配，T称为模式。
暴力匹配（朴素模式匹配BF）
规定i是主串S的下标，j是模式T的下标。现在假设现在主串S匹配到 i 位置，模式串T匹配到 j 位置。
如果当前字符匹配成功（即S[i] = T[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i] != T[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯到本次失配起始字符的下一个字符，j 回溯到0。

int BF(char S[],char T[])
{
	int i=0,j=0;
	while(S[i]!='\0'&&T[j]!='\0')
	{
		if(S[i]==T[j])
		{
			i++;
			j++;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(T[j]=='\0') return (i-j);     //主串中存在该模式返回下标号 
	else return -1;     //主串中不存在该模式 
}

1. 背景KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。

前缀与后缀
前缀：含有首字符不含尾字符的所有子串。
后缀：含有尾字符不含首字符的所有子串。
最长相等前后缀的长度next数组
现在有串P=abaabca，各个子串的最大相等前后缀长度如下表所示：

 这样，最长相等前后缀最长长度就会和串P的每个字符产生一种对应关系：

 这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。

接下来我们就用这个表来引出next数组，next 数组的值是公共前后缀最长长度。我们称next数组中的值为失效函数值。

#include
#include
using namespace std;
void getnext(int *next,string &s)
{
	int i,j;
	next[0]=0;
	j=0;
	for (int i=1;i0&&s[j]!=s[i])
		{
			j=next[j-1];
		}
		if (s[j]==s[i]) j++;
		next[i]=j;
	}
}
int Kmp(string s,string t)
{
	int *next;
	next= new int [s.size()+1];
	getnext(next,s);
	int i=0,j=0;
	for (i=0;i0&&s[j]!=t[i])
		{
			j=next[j-1];
		}
		if (s[j]==t[i]){
			j++;
		}
		if (j==s.size())
		{
			return i-j+1;
		}
	}
	return -1;
}
int main()
{
	string s,t;
	cin>>t;
	cin>>s;
	cout<