KMP算法下面只写个代码, 网上有很多讲解(还没见一个讲得很清楚的, 用文字也确实难讲清楚), 想学习的直接看严大妈的视频讲解严蔚敏KMP讲解, 多看几遍总能懂.
typedef char String[225];
// get_next数组
void get_next(String T, int *next) {
int i = 1;
int j = 0;
next[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++i;
++j;
if (T[i] != T[j]) next[i] = j;
else T[i] = next[j];
} else {
j = next[j];
}
}
}
int get_KMP(String S, String T, int pos) {
int i = pos;
int j = 1;
int next[255];
get_next(T, next);
while (i <= S[0] && j <= T[0]) {
if (j == 0 || T[j] == S[i]) {
++i;
++j;
} else {
j = next[j];
}
}
if (i > S[0]) {
return 0;
} else {
return i - T[0];
}
}
