260724strC CF1721E KMP自动机学习笔记

许卿安 · 2026-07-24 12:00:49 · 题解

KMP 自动机模板题。前置知识：KMP。

如果每次暴力 KMP 求解，时间复杂度 O(q|s|)，无法通过。考虑如何优化。

首先可以发现，s 串中的 nxt 是固定的，所以我们只需要从两串拼接处开始 KMP 即可。但是这样仍然会超时，因为沿着失配数组往前跳依然是 O(|s|) 的。

观察我们从 i 开始往前跳的过程。注意到我们最终跳到的 j 一定满足 s_{j+1}=s_i，于是我们用一个数组 tr_{i,c} 记录下“由位置 i 开始不断沿着失配数组往前跳，跳到的第一个满足 s_{j+1}=c 的 j”。（若该值不存在则为 0。）

那么我们有转移：

那么对于当前指针 j，我们可以直接找到继续进行匹配的位置 tr_{j,s_i}+1。注意要特判 tr_{j,s_i}=0 的情况。随后，我们要更新 nxt_i 和 tr_{i-1,c}。

时间复杂度为 O(|s|+\sum|t|)。需要注意的是，字符串赋值的时间复杂度是 O(n) 级别的，本题中如果用一个临时串存储原始 s，在每次操作后用该串给 s 赋值，那么时间复杂度变为 O(q|s|)，仍会 TLE。

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

const int N=1e6+1e5+2;
int nxt[N];
int tr[N][30];

//tr[i][j] 表示 不停沿着 nxt[] 往上跳，使得 s_{k+1}=j 的 k

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    string s;cin>>s;int n=s.size();s=" "+s;
    for(int i=1,j=0; i<=n; ){
        if(!j || s[i]==s[j]) nxt[++i]=++j;
        else j=nxt[j];
    }
    for(int i=1; i<=n; i++) nxt[i]=nxt[i+1]-1;
    for(int i=0; i<n; i++){
        for(int c=0; c<26; c++) tr[i][c]=tr[nxt[i]][c];
        tr[i][s[i+1]-'a']=i;
    }
    int q;cin>>q;
    while(q--){
        string t;cin>>t;int m=t.size();s+=t;
        for(int i=n+1,j=nxt[n]; i<=n+m; i++){
            j=tr[j][s[i]-'a']+1; // s_j=s_i / tr_{...}=0
            if(s[i]!=s[j]) j=0; // 特判！
            nxt[i]=j;cout<<j<<" ";
            for(int c=0; c<26; c++) tr[i-1][c]=tr[nxt[i-1]][c];
            tr[i-1][s[i]-'a']=i-1;
        }
        for(int i=n+1; i<=n+m; i++) s.pop_back();
        cout<<"\n";
    }
    return 0;
}