kmp关于next数组和周期

如果不了解kmp算法，可以看一下这篇文章：点击打开链接

在kmp算法中，有两种方法求next数组，一种是：

void pre(int len)
{
	int i = 0, j = -1;
	next[0] = -1;
	while(i != len)
	{
		if(j == -1 || pattern[i] == pattern[j])
			next[++i] = ++j;
		else
			j = next[j];
	}
}

另一种是：

void pre(int len) //前缀函数(滑步函数)
{
	int i = 0, j = -1;
	next[0] = -1;
	while(i != len)
	{
		if(j == -1 || pattern[i] == pattern[j]) //(全部不相等从新匹配 || 相等继续下次匹配)
		{
			++i, ++j;
			if(pattern[i] != pattern[j]) //abcdabce
				next[i] = j;
			else //abcabca
				next[i] = next[j];
		}
		else
			j = next[j]; //子串移动到第nextval[j]个字符和主串相应字符比较
	}
}

在求前缀和后缀的最大匹配值时，要用第一种。在运用kmp时要用第二种，效率更高。

一个串的最小循环节长度是：len-next[len]。

如果len%(len-next[len])==0，那么这个字符串的最小周期就是：len/(len-next[len]).

kmp关于next数组和周期,布布扣,bubuko.com

kmp关于next数组和周期

原文：http://blog.csdn.net/crescent__moon/article/details/22093565