KMP算法；学习严蔚敏；大概理解；

#include<iostream>
#include<vector>
#include<string>
usingnamespacestd;

strings;//主串
stringt;//模式串
vector<int>next;//next函数值
vector<int>nextval;//next修正函数值

voidget_next()
{
inti=1;
intj=0;
next[1]=0;

while(i<(int)t.size()-1)
{
if(j==0||t[i]==t[j])//i指针不回溯
{
++i;
++j;
next[i]=j;
}
else//如果不相等,则j根据已求next回溯,或者找到t[i]==t[j]且j不能再大，则next[++i]=next[++j]，或者j==0，则没有能匹配相等的，则++i,++j
{
j=next[j];
}
}
}

voidget_nextval()
{
inti=1;
intj=0;
nextval[1]=0;
while(i<(int)t.size()-1)
{
if(j==0||t[i]==t[j])
{
++i;
++j;
if(t[i]!=t[j])
{
nextval[i]=j;
}
else
{
nextval[i]=nextval[j];
}
}
else
{
j=nextval[j];
}
}
}

intindex_kmp(intpos)
{
inti=pos;
intj=1;
while(i<=(int)s.size()-1&&j<=(int)t.size()-1)
{
if(j==0||s[i]==t[j])
{
++i;
++j;
}
else
{
j=nextval[j];
}
}

if(j>(int)t.size()-1)
{
returni-((int)t.size()-1);
}
else
{
return0;
}
}

intmain()
{
stringtemp;
s.push_back('#');
t.push_back('#');
cout<<"输入主串:";
getline(cin,temp);
s+=temp;
cout<<"输入模式串:";
getline(cin,temp);
t+=temp;
next.assign(t.size()+1,0);
nextval.assign(t.size()+1,0);
//以上为输入部分
get_nextval();
cout<<index_kmp(1)<<endl;

}

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

string s;//主串
string t;//模式串
vector<int> next;//next函数值
vector<int> nextval;//next修正函数值

void get_next()
{
	int i=1;
	int j=0;
	next[1]=0;

	while(i<(int)t.size()-1)
	{
		if(j==0||t[i]==t[j])//i指针不回溯
		{
			++i;
			++j;
			next[i]=j;
		}
		else//如果不相等,则j根据已求next回溯,或者找到t[i]==t[j]且j不能再大，则next[++i]=next[++j]，或者j==0，则没有能匹配相等的，则++i,++j
		{
			j=next[j];
		}
	}
}

void get_nextval()
{
	int i=1;
	int j=0;
	nextval[1]=0;
	while(i<(int)t.size()-1)
	{
		if(j==0||t[i]==t[j])
		{
			++i;
			++j;
			if(t[i]!=t[j])
			{
				nextval[i]=j;
			}
			else
			{
				nextval[i]=nextval[j];
			}
		}
		else
		{
			j=nextval[j];
		}
	}
}

int index_kmp(int pos)
{
	int i=pos;
	int j=1;
	while(i<=(int)s.size()-1&&j<=(int)t.size()-1)
	{
		if(j==0||s[i]==t[j])
		{
			++i;
			++j;
		}
		else
		{
			j=nextval[j];
		}
	}

	if(j>(int)t.size()-1)
	{
		return i-((int)t.size()-1);
	}
	else
	{
		return 0;
	}
}

int main()
{
	string temp;
	s.push_back('#');
	t.push_back('#');
	cout<<"输入主串:";
	getline(cin,temp);
	s+=temp;
	cout<<"输入模式串:";
	getline(cin,temp);
	t+=temp;
	next.assign(t.size()+1,0);
	nextval.assign(t.size()+1,0);
	//以上为输入部分
	get_nextval();
	cout<<index_kmp(1)<<endl;
	
}

以下i表示主串位置，j表示模式串位置,s为主串，t为模式串.

KMP算法的牛逼之处就是免去i的回溯, 否则普通的扫描扫着扫着不相等,i又回溯到之前的起始位置的下一个位置,j也回溯到1，又开始匹配.

而KMP则是i一直向前走,一旦遇到不匹配的字符,j回溯到一个可以用来比较的位置，而j之前的t部分串与s串i之前的部分是最大匹配的,然后检测s[i],t[j]是否相等,相等则i可以+1，j+1，继续检测，此时i能够后移的原因是，i之前的部分串已最长的匹配t串,这种理解只可意会,不可言传....

next的作用： 当扫描过程中,如果s[i]!=t[j],那么j=next[j]，然后比较s[i]与t[j]，此时.....s[i-1]与......t[j-1]是最长匹配的,如果s[i]==t[j],那么++i,++j,继续扫描下一位，如果不相等，那么继续j=next[j],再找一个次长的匹配，比较s[i]与s[j]，如果一直到j==0都没有匹配i位的字符，那么说明整个模式串与s[i]以及之前的一段都没有匹配，则++i,++j， 即继续从j=1,i=i+1比较。

next怎么求的：这个非常飘渺, next只与模式串有关，因为在s与t匹配过程中一旦遇到一个字符不匹配，那么就应该尝试用已经匹配的那一段t与已经匹配的s的部分去匹配，然后比较t的部分匹配的下一个位置与s[i]是否相等. 所以求next就相当于t与t进行匹配的过程, 与KMP算法非常类似的,首先令i=1,j=0,next[1]=0，表示如果t[1]与主串的字符不匹配，那么应该去和t[0]比较且t[0]之前部分匹配，但是t[0]没有字符，所以if j==0, ++i,++j, 这一位t[i]已经没法匹配了。 如果t[i]与t[j]，则++i,++j，并且++i,++j之前的i,j之前的段属于匹配的，所以++i,++j以后的next[i]=j,即如果s[某一位]与t[i]不相等，那么就可以根据next[i]找到j，用s[某一位]与t[j]比较看是否相等.

nextval怎么求：这个是next的升级版，思想是建立在next之上的，但是并不是说要先求next才能求nextval， nextval只是在next的思想上进一步优化了。 如果求next的过程中，t[i]==t[j]，那么本来可以直接写 next[++i]=++j; 但是这时候有一些问题，如果t[++i]与主串s[某位]不相等的时候，我们用next[++i]，结果t[next[++i]]与t[++i]又相等，虽然i之前的t串与s串某一位之前完全匹配，但是这样的比较是没有意义的，因为既然匹配过程中已不相等，根据next滑动t串后的比较位与t之前的比较位一样，肯定也不匹配，所以这时候我们就非常需要nextval发挥作用了。 所以如果求next的过程中，t[++i]==t[++j],那么我们应该让j回溯到nextval[j]以找到一个不相等的位匹配,这样就最终求得了nextval的所有情况.

的确是只可意会不可言传，权当自己的思路笔记了。。。。。。。。。。不指望别人能读懂