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]