KMP模版题(洛谷P3375 KMP字符串匹配)

mac2024-01-23  27

KMP模版题(洛谷P3375 KMP字符串匹配)

题目

见题目链接 题目链接【模板】KMP字符串匹配 - 洛谷

输入

见题目链接

输出

见题目链接

样例

见题目链接

题解

一个标准的KMP模版。 具体算法原理参考:很详尽KMP算法(厉害) - ZzUuOo666 - 博客园 无论是原理,还是实现,都写得十分详细、易懂。

代码

#include <stdio.h> void GetNext(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while(j < pLen) { if (k == -1 || p[j] == p[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } void KMP(char* p1, char* p2, int next[]) { int p1Len = strlen(p1); int p2Len = strlen(p2); int i,j; i = 0; j = 0; while (i < p1Len) { if (j == -1 || p1[i] == p2[j]){ i++; j++; } else j = next[j]; if (j == p2Len){ printf("%d\n", i - p2Len + 1); j = next[j]; } } } int main(){ char s1[1000005],s2[1000005]; int next[1000005]; scanf("%s", s1); scanf("%s", s2); GetNext(s2, next); KMP(s1, s2, next); int len = strlen(s2); for (int i = 1;i < len; i++) printf("%d ", next[i]); printf("%d", next[len]); return 0; }

代码解释

求next数组(字串的前缀数组):

void GetNext(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while(j < pLen) { if (k == -1 || p[j] == p[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } }

Next数组的首元素是-1,可以看作是子串(模式串)各个位置对应的各个前缀后缀的公共元素的最大长度表向右移一位,并将多出来的首位置为-1。两者可以相互转换,在KMP中的使用分别如下: 根据最大长度表,失配时,模式串向右移动的位置 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值。 根据next数组,失配时,模式串向右移动的位置 = 失配字符的位置 - 失配字符对应的next值。 简单计算可得,这两者是等价的。 具体的求next数组的原理在“题解”部分给出的链接里有详细说明,在此不多赘述。

KMP匹配:

void KMP(char* p1, char* p2, int next[]) { int p1Len = strlen(p1); int p2Len = strlen(p2); int i,j; i = 0; j = 0; while (i < p1Len) { if (j == -1 || p1[i] == p2[j]){ i++; j++; } else j = next[j]; if (j == p2Len){ printf("%d\n", i - p2Len + 1); j = next[j]; //在完成一次完全匹配后,模式串需要向右移动一定的距离,效果等价于在模式串的最后一个元素的位置失配。 } } }

仔细观察会发现这部分的代码与求next数组的代码十分相似,其实求next数组的过程可以看成是在进行两个模式串在互相匹配,其中通过调用已求得的next数组来进行回溯可以看作是模式串与主串匹配过程中通过next数组回溯到模式串中的某个位置。

最新回复(0)