!!! 注意: 此图是本书中使用的自定的串结构, 下标从1开始的 , 下方代码是使用C风格字符串, 下标从0开始的, 因此上述next[j] 公式修改如下:
KMP 算法代码实现:
以普通的C风格字符串作为例子。
#include <stdio.h>
#include <
string.h>
#include <stdlib.h>
#define NDEBUＧ /*需要调试信息输出请注释此宏*/
/*获取next数组*/
void get_next(
const char *t,
int *
next)
{
int i,j;
i =
0;
j = -
1;
/*调整j为-1，代表主串从失配位置下一个位置 在 和模式串重头开始匹配*/
next[0] = -
1;
int t_len =
strlen(t);
while(i <
t_len)
{
if(-
1 == j || t[i] ==
t[j])
{
++
i;
++
j;
next[i] =
j;
}else{
j =
next[j];
}
}
}
/*匹配, 在main串中匹配pattern*/
int subString(
const char *s,
const char *
t)
{
int i =
0;
/*指向mian串字符位置的指针*/
int j =
0;
/*指向pattern串字符位置的指针*/
int s_len =
strlen(s);
int t_len =
strlen(t);
int * next = (
int *)
malloc(
sizeof(
int) *
(t_len));
get_next(t, next);
while(i < s_len && j <
t_len)
{
/*等于-1 说明将i+1的位置 和 模式串的0位置的字符串在进行匹配就行了*/
if( -
1 == j || s[i] ==
t[j])
{
i++
;
j++
;
}
else /*失配调整位置*/
{
/*下方代码块儿 输出调试信息, 方便理解KMP算法 , 可以删除*/
{
#ifndef NDEBUG
int len = i -
j;
int k;
printf("-------------------lose--------------------------\n");
printf(" i : %d -- j : %d \n", i, j);
printf("%s\n", s);
for(k =
0; k<i;++
k)
printf(" ");
printf("^\n");
for(k =
0; k<len;++
k)
printf(" ");
printf("%s\n", t);
printf("--------------------------------------------------\n");
#endif
}
j =
next[j]
}
}
free(next);
if(j >=
t_len)
return i -
t_len;
else
return -
1;
}
int main()
{
const char *t =
"abcade";
const char *s =
"abxabdabcade";
int result =
subString(s, t);
printf("%d\n",result);
return 0;
}
KMP
KMP优化:
例子1:
s : a a a a a a b c x a a a a a a a
t : a a a a a a a
next[t] = -1 0 1 2 3 4 5
如上方的例子:
在 i = 5 且 j = 5 的位置发生了失配, 那么 j 会调整到 j = 4 继续 与 i = 5 匹配 又发生失配, j又
调整到 j = 3 一直调整到 j = 0 的时候-1标志才会让 i 加1, 进而完成一次 I的调整 。可见从
s[5] != t[5] 的那次失配的其, next调整到4, 3 , 2 , 1 完全是多余的, 直接调整到 0 就行啦。
则
那么求next数组的算法进行如下优化:
void get_next(
const char *T,
int *
next)
{
int i =
0, j = -
1;
next[0] = -
1;
while(i <
strlen(T))
{
// T[i] 表示后缀的单个字符
// T[j] 表示前缀的单个字符
if(j == -
1 || T[i] ==
T[j])
{
++
i;
++
j;
if(next[i] !=
next[j])
next[i] =
j;
else
next[i] =
next[j];
}
else
j =
next[j];
}
}
KMP优化
转载于:https://www.cnblogs.com/Geek-Z/p/10089279.html
相关资源：JAVA上百实例源码以及开源项目
