本节主要讨论字符串的匹配问题, 也就是说, 如果给出两个字符串 text 和 pattern, 需要判断字符串 pattern 是否是字符串 text 的子串
一 next 数组
next[i] 表示使子串 s[0...i] 的前缀 s[0...k] 等于后缀 s[i-k...i] 的最大的 k; 如果找不到相等的前后缀, 那么令 next[i] = -1 显然, next[i] 就是所求最长前后缀中前缀最后一位的下标
next 数组的求解过程如下:
初始化 next 数组, 令 j = next[0] = -1
让 i 在 1~len-1 范围遍历, 对每个 i, 执行 34, 以求解 next[i]
不断令 j=next[j], 直到 j 回退到 -1, 或是 s[i] == s[j+1] 成立
如果 s[i] == s[j+1], 则 next[i] = j+1; 否则 next[i] = j
代码如下:
- // 求解长度为 len 的字符串 s 的 next 数组
- void getNext(char s[], int len) {
- int i,
- j = -1;
- next[0] = -1; // 初始化 j=next[0]=-1
- for (i = 1; i < len; ++i) { // 求解 next[i]
- // 循环直到 j 回退到 -1, 或是 s[i] == s[j+1] 成立
- while (j != -1 && s[i] != s[j + 1]) {
- j = next[j];
- }
- if (s[i] == s[j + 1]) { // 若 s[i] == s[j+1]
- j++; // next[i] = j+1
- }
- next[i] = j; // 否则 next[i] = j
- }
- }
二 KMP 算法
以下为 KMP 算法的一般思路:
初始化 j=-1, 表示 pattern 当前已被匹配的最后位
让 i 遍历文本串 text, 对每个 i, 执行 34 来试图匹配 text[i] 和 pattern[j+1]
不断令 j = next[j], 直到回退为 -1, 或是 text[i] == pattern[j+1] 成立
如果 text[i] == pattern[j+1], 则令 j++ 如果 j 达到 m-1, 说明 pattern 是 text 的子串, 返回 true
代码如下:
- // 判断 pattern 是否是 text 的子串
- int KMP(char text[], char pattern[]) {
- int n=strlen(text), m=strlen(pattern); // 字符串长度
- getNext(pattern, m); // 求 next 数组
- int i, j = -1;
- for(i=0; i<n; ++i) { // 试图匹配 text[i]
- while(j!=-1 && text[i]!=pattern[j+1]) {
- j = next[j];
- }
- if(text[i] == pattern[j+1]) {
- j++; // 匹配成功, j+1
- }
- if(j == m-1) { // 完全匹配
- return 1;
- }
- }
- return 0;
- }
接下来考虑如何统计文本串 text 中模式串 pattern 出现的次数代码如下:
- // 统计 pattern 在 text 中出现的次数
- int KMP(char text[], char pattern[]) {
- int n=strlen(text), m=strlen(pattern); // 字符串长度
- getNext(pattern, m); // 求 next 数组
- int i, ans=0, j = -1; // ans 存储 pattern 出现的次数
- for(i=0; i<n; ++i) { // 试图匹配 text[i]
- while(j!=-1 && text[i]!=pattern[j+1]) {
- j = next[j];
- }
- if(text[i] == pattern[j+1]) {
- j++; // 匹配成功, j+1
- }
- if(j == m-1) { // 完全匹配
- ans++; // 成功匹配次数 +1
- j = next[j]; // 继续匹配
- }
- }
- return ans;
- }
完整测试代码如下:
- /*
- KMP 算法
- */
- #include < stdio.h > #include < string.h > #include < math.h > #include < stdlib.h > #include < time.h > #define maxn 100 int next[maxn];
- // 求解长度为 len 的字符串 s 的 next 数组
- void getNext(char s[], int len) {
- int i,
- j = -1;
- next[0] = -1; // 初始化 j=next[0]=-1
- for (i = 1; i < len; ++i) { // 求解 next[i]
- // 循环直到 j 回退到 -1, 或是 s[i] == s[j+1] 成立
- while (j != -1 && s[i] != s[j + 1]) {
- j = next[j];
- }
- if (s[i] == s[j + 1]) { // 若 s[i] == s[j+1]
- j++; // next[i] = j+1
- }
- next[i] = j; // 否则 next[i] = j
- }
- }
- // 统计 pattern 在 text 中出现的次数
- int KMP(char text[], char pattern[]) {
- int n = strlen(text),
- m = strlen(pattern); // 字符串长度
- getNext(pattern, m); // 求 next 数组
- int i,
- ans = 0,
- j = -1; // ans 存储 pattern 出现的次数
- for (i = 0; i < n; ++i) { // 试图匹配 text[i]
- while (j != -1 && text[i] != pattern[j + 1]) {
- j = next[j];
- }
- if (text[i] == pattern[j + 1]) {
- j++; // 匹配成功, j+1
- }
- if (j == m - 1) { // 完全匹配
- ans++; // 成功匹配次数 +1
- j = next[j]; // 继续匹配
- }
- }
- return ans;
- }
- int main() {
- char text[maxn],
- pattern[maxn];
- while (scanf("%s %s", text, pattern) != EOF) {
- // 输出匹配次数
- printf("ans=%d\n", KMP(text, pattern));
- }
- return 0;
- }
输入:
abababab abab
输出:
3
来源: http://www.bubuko.com/infodetail-2497229.html