学步园

     KMP算法是字符串匹配的经典算法，由于其O(m+n)的时间复杂度，至今仍被广泛应用。由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串定义一个next函数。next函数包含了模式串本身局部匹配的信息。
                                 

       其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。

   j               |   1  2  3  4  5

模式            |   a  a  a  a  b

next[j]          |   0  1  2  3  4        带有缺陷的next

nextval[j]     |   0  0  0  0  4         修正后的next

具体实现代码如下：（参照《数据结构（C语言版）》串操作）

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

ifstream fin("in.txt");

int next[100]={0};

void get_next(string t)
//求模式串t的next函数修正值
{
	int i=0;
	int j=-1;
	next[0]=-1;
	int tn = t.size();
	while(i<tn)
	{
		if(j==-1 || t[i]==t[j])
		{
			i++; j++;
			if(t[i]!=t[j])next[i]=j;
			else next[i]=next[j];
		}
		else j = next[j];
	}
	return;
}

int Index_KMP(string s,string t,int pos)
{
	//利用模式串的next函数求t在主串s中第pos个字符之后的位置的KMP算法。
	//0 =< pos <= s.size();
	int i = pos;
	int j = 0;
	int sn = s.size();
	int tn = t.size();
	while(i<sn && j<tn)
	{
		if(j==-1 || s[i]==t[j]){i++;j++;}  //若j==-1 表示已回溯到第一个仍不相等则下一个；若s[i]==t[j]表示当前字符匹配成功，下一个
		else j=next[j];						//模式串向右移动
	}
	if (j>=tn)return i-tn;					//匹配成功
	else return 0;
}

int main()
{
	string s,t;
	fin>>s>>t;
	get_next(t);
	for(int i=0;i<t.size();i++)
		cout<<next[i]<<" ";
//	cout<<"find t from s : "<<s.find(t,0)<<endl;
	cout<<"KMP:"<<Index_KMP(s,t,0)<<endl;
	return 0;
}