字符串（一）KMP，Trie，AC自动机

DF_G · 2026-09-28 15:34:29 · 算法·理论

前言

::::info[AI使用声明] 本文使用了 deepseek 润色，保证人类贡献远大于 AI 贡献。（deepseek 基本删除了所有前言以外的“喵”伤心喵。） :::: ::::info[一些废话] 串串可爱喵。串串吃智商喵。（难过）\ 一觉醒来忘记了所有关于串串的知识，于是大复习了一遍。 :::: 这篇文章实质上是一篇超短的学习笔记喵。

KMP

Problem:\ 给定下面的两个字符串：

• 文本串 T，长度为 n，下标为 1,\dots,n。
• 模式串 P，长度为 m，下标为 1,\dots,m。

要求找到所有位置 i 使得 T_{i,\dots,i+m-1}=P_{1,\dots,m}，即 P 在 T 中每一次完整出现的位置。

一个暴力做法是：对于每一个起点 i，逐字符比较 T_{i+j-1} 和 P_j（1\le j\le m），时间复杂度是 O(nm) 的。暴力的问题在于，一旦失配，之前已经比较过的信息全部丢弃，需要从头重新比较。

对于模式串 P，定义数组 \text{next}_{1,\dots,m}，其中 \text{next}_i 表示 P_{1,\dots,i} 的所有真前缀中最长的、同时也是 P_{1,\dots,i} 真后缀的长度，即

空串是任何字符串的前缀和后缀，因此 \text{next}_i\ge 0。注意 k<i，因为要求的是真前缀和真后缀。由定义可得 \text{next}_1=0。

::::info[为什么要这样定义？]{open} 匹配失配时，我们希望把模式串尽量少地往后滑动，同时保证已经匹配的部分仍然匹配。\text{next}_i 表示的是：P_{1,\dots,i} 的前缀可以和后缀对齐的最大长度。这样滑动之后，这一段已经和文本串匹配过，不需要重新比较。 ::::

假设 \text{next}_1,\dots,\text{next}_{i-1} 已经全部求出来了，设 j=\text{next}_{i-1}，那么有 P_{1,\dots,j}=P_{i-j,\dots,i-1}。接下来要把 P_i 接上去：

• 如果 P_{j+1}=P_i，那么 P_{1,\dots,j+1}=P_{i-j,\dots,i}，所以 \text{next}_i=j+1。
• 如果 P_{j+1}\ne P_i，说明以 j+1 为长度不行，需要找到一个更短的、同时是 P_{1,\dots,i-1} 一个真后缀的前缀。这个前缀就是 \text{next}_j。因为 P_{1,\dots,j}=P_{i-j,\dots,i-1}，所以 P_{1,\dots,i-1} 的任何一个后缀如果是前缀，那么也一定是 P_{1,\dots,j} 的后缀，同时是 P_{1,\dots,j} 的前缀。

::::info[解释]{open} 由 \text{next}_{i-1} 的定义可以得到

设要求的 \text{next}_i 对应的最长长度为 k，那么

寻找的 k<j+1（如果 P_{j+1}\ne P_i），那么 k\le j。②的 P_{1,\dots,k} 是 P_{1,\dots,j} 的前缀。\

把所有规则的 \text{exc}(s1, s2) 插入 AC 自动机。对每个询问，跑一遍 \text{exc}(t1, t2)，统计有多少个规则串作为子串出现。 ::::success[P14363]

#include<bits/stdc++.h>
using namespace std;

const int N = 5e6 + 10;

int n,tot,pid,Q;
int cnt[N];
struct node {
    int son[27];
    int fail;
    int id;
} tr[N];

void build(string t,int &idx) {
    int len = t.size(),u = 0;
    for(int i = 0;i < len;i++) {
        if(!tr[u].son[t[i] - 'a']) tr[u].son[t[i] - 'a'] = ++tot;
        u = tr[u].son[t[i] - 'a'];
    }
    if(!tr[u].id) tr[u].id = ++pid;
    idx = tr[u].id;
    cnt[u]++;
}

queue<int> q;
void Fail() {
    for(int i = 0;i < 27;i++) if(tr[0].son[i]) q.push(tr[0].son[i]);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        cnt[u] += cnt[tr[u].fail];
        for(int i = 0;i < 27;i++) {
            if(tr[u].son[i]) {
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                q.push(tr[u].son[i]);
            } else tr[u].son[i] = tr[tr[u].fail].son[i];
        }
    }
}

int query(string t) {
    int u = 0,res = 0,len = t.size();
    for(int i = 0;i < len;i++) {
        u = tr[u].son[t[i] - 'a'];
        res += cnt[u];
    }
    return res;
}

string exc(string s1,string s2) {
    int len = s1.size(),l = 0,r = len - 1;
    for(int j = 0;j < len;j++) if(s1[j] != s2[j]) { l = j; break; }
    for(int j = len - 1;j >= 0;j--) if(s1[j] != s2[j]) { r = j; break; }
    string s = "";
    for(int j = 0;j < l;j++) s += s1[j];
    s += '{';
    for(int j = l;j <= r;j++) s += s1[j];
    for(int j = l;j <= r;j++) s += s2[j];
    s += '{';
    for(int j = r + 1;j < len;j++) s += s1[j];
    return s;
}

signed main() {
    scanf("%d%d",&n,&Q);
    for(int i = 1;i <= n;i++) {
        string s1,s2;
        cin >> s1 >> s2;
        int id;
        build(exc(s1,s2),id);
    }
    Fail();
    while(Q --) {
        string t1,t2;
        cin >> t1 >> t2;
        if(t1.size() != t2.size()) { puts("0"); continue; }
        printf("%d\n",query(exc(t1,t2)));
    }
    return 0;
}

::::