KMP算法的理解
参考:
https://www.zhihu.com/question/21923021/answer/281346746 @海纳 大大讲解得十分清楚,就不重复造轮子了
https://www.cnblogs.com/cherryljr/p/6519748.html 这里的nextval讲的清楚,但是前面太罗嗦,建议跳转nextval挑着看
还借鉴了一点《大话数据结构》,但是它太罗嗦,没看下去的兴趣和耐心,而且和我的next数组定义上有点出入……
要点
- PMT(Partial Match Table)数组,储存前缀后缀交集最长的长度
- next数组即PMT数组右移一位,是为了编程方便,
next[j] = PMT[j-1]
- next数组的求值,用pattern串和pattern串匹配求得会方便很多
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include<cstdio> #include<cstring>
const int MAX_N = 1e5; const int MAX_M = 1e2;
char strt[MAX_N]; char strp[MAX_M]; int next[MAX_M+2];
void getnext() { next[0] = -1; int i = 0; int j = -1; int len = strlen(strp);
while(i < len) { if(j == -1 || strp[i] == strp[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } }
int kmp() { int i = 0; int j = 0;
int len1 = strlen(strt); int len2 = strlen(strp);
while(i < len1 && j < len2) { if(j == -1 || strt[i] == strp[j]) { i++; j++; } else j = next[j]; } if(j == len2) return i - j; else return -1; }
int main() { scanf("%s", strt); scanf("%s", strp); getnext(); int ans = kmp(); printf("%d\n", ans); return 0; }
|
改进
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| text = "aaaabcde" pattern = "aaaaax" next[] = -1, 0, 1, 2, 3, 4, 0 NO1. aaaabcde aaaaa NO2. aaaabcde aaaa NO3. aaaabcde aaa …… 可以看出,因为存在重复的连续序列,所以存在重复匹配 我们希望的是 NO1. aaaabcde aaaaa NO2. aaaabcde a 于是改进后的next数组即nextval数组来了
|
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void get_nextval() { nextval[0] = -1; int i = 0; int j = -1; int len = strlen(strp);
while(i < len) { if(j == -1 || strp[i] == strp[j]) { ++i; ++j; if(strp[i] != strp[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } }
|
上面*
注释的解释
例如ababzababx和ababx匹配
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| NO1. ababzababx ababx NO2. ababzababx aba NO3. ababzababx a 可以看出,NO1先回退到next[j]再回退到next[next[j]]; 所以把next[next[j]]赋值给next[i]即可以一步到位 区分以下两行 next[i] = j; nextval[i] = nextval[j]; 为什么没有nextval[i] = nextval[nextval[j]]呢? 因为是从前往后一步步推过来的,每一步的nextval[i]都是i点匹配失败时回退到的最优点(动态规划思想)
|
优化后的匹配过程
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| a a a a a x next -1 0 1 2 3 4 nextval -1 0 0 0 0 4 NO1. aaaabcde aaaaa NO2. aaaabcde a a b a b a a a b a next -1 0 1 2 3 1 1 2 3 nextval -1 0 1 0 1 0 0 0
|
结尾
至此,kmp算法和kmp算法的优化已经完成
真是不容易……
又该补题了