JAVA字符串算法——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]