KMP 字符串匹配

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 797 字

next 数组跳过已匹配，失配回退最长前缀

字符串
KMP

前置内容

子串与回文判断

正文

// KMP：高效字符串匹配
// 用 next 数组跳过已匹配
// 失配时回退到最长前缀
// 例：统计模式串出现次数
#include <cstdio>
#include <cstring>
char s[1000005], p[1000005];
int ne[1000005], n, m;
// 求模式串的 next 数组
void get_ne() {
    ne[1] = 0;
    // j 为当前匹配长度
    for (int i = 2, j = 0; i <= m; i++) {
        // 失配则缩短前缀
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
}
int main() {
    scanf("%s%s", s + 1, p + 1);
    n = strlen(s + 1);
    m = strlen(p + 1);
    get_ne();
    // 主串上做同样匹配
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1]) j++;
        // 匹配完一次，回退继续
        if (j == m) {
            printf("%d ", i - m + 1);
            j = ne[j];
        }
    }
    return 0;
}

KMP 字符串匹配

前置内容

正文

CSP-J · 编程模板的其它内容