字符串算法――KMP算法

KMP算法是对字符串匹配算法的一个重大改进 ， 创造性的利用子串本身的特性 ， 来改进算法的效率。

KMP算法的关键或则精华 ， 就是在与 next[ ] 的计算。

假设存在主串 S 和 子串 T ， 我们在某一趟匹配中 ， 发现 T(k) != S(i+1)

那我们就得到了一个部分的匹配结果

即：T(1).......T(k-1) = S(i-k+1) ...... S(i-1)

我们假设存在一个 j < k 使得： T(1)......T(j-1) = S(i-k+1).....S(i-k+j-1)

也就是说 T(1).......T(j-1) = T(k-j).........T(k-1)

所以这时我们就需要把子串向右移动 k-j 位 ， 而如果 此时不存在这样的情况 ， 也就是 j = 0 ， 那么我们就需要向右移动 k 位

因此我们只需要求出子串中每个位置对应的 j 既可

这就是KMP算法的思想

因此next() 函数的定义如下：

0 j = 1 时

next（）= max( k / 1<=k

1 当不存在上面的K且T(1) != T(j)

0 当不存在上面的K且T(1) != T(i)

求next() 函数的代码如下：

char s[100]; //被匹配字符串
char t[100]; //匹配字符串
int next[100];  //存储匹配串中每个字符应移的距离
int s_length , t_length;//被匹配串和匹配串的字符长度

void getnext()
{
	int i = 0, j =-1;
	next[i] = -1;
	while(i < t_length)
	{
		while(j >= 0 && t[i] != t[j])  j = next[j]; //和该字符前面的字符比较 ， 看是否和前面的字符相同
		
		i++;  j++;

		if(t[i] == t[j])  next[i] = next[j];//如果当前两字符相同 ， 
		else next[i] = j;
	}
	for(i = 0; i < t_length; i++)
		printf("%d\n" , next[i]);
}
//向右滑动的距离为：j-next[j]