KMP(next)模板

为方便计算，统一从下标1开始。

class mystring
{
public:
	char ch[maxsize];
	int length;
};
void get_next(char *nextt,mystring &T)
{
	int i = 1, j = 0;
	nextt[1] = 0;	//初始化
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			i++, j++; nextt[i] = j;
		}
		else
			j = nextt[j];	//不匹配  j回溯
	}
}
//求T在S中第一个位置Index
int KMP(char *nextt, mystring &S, mystring &T)
{
	int i = 1, j = 1;
	while (i <= S.length&&j <= T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j])
		{
			i++; j++;
		}
		else
			j = nextt[j];	//不匹配  j回溯
	}
	if (j > T.length)return i - T.length;//j
	else return 0;
}
int main()
{
	mystring S, T;
	cin >> S.ch+1 >> T.ch + 1;
	S.length = strlen(S.ch + 1);
	T.length = strlen(T.ch + 1);
	char next[maxsize] = { 0 };
	get_next(next, T);
	cout<<"KMP:"< 
//求T在S中的所有位置
void KMP(char *nextt, mystring &S, mystring &T)
{
	int i = 1, j = 1;
	while (i <= S.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j])
		{
			i++; j++;
		}
		else
			j = nextt[j];	//不匹配  j回溯
		if (j > T.length)	//找到匹配位置Index
		{
			cout << i - T.length << endl;
			i = i - T.length + 1;	//i j 回溯 
			j = 1;
		}
	}
}