0. 前言

你需要知道的芝士：

AC 自动机基础；
Trie 树；

这里是进阶使用，所以会结合一些例题来讲解，读者应有 AC 自动机的基础芝士即可。

1. 自动机与 AC 自动机本质

考虑到大多数都是先学 AC 自动机，而很久以后才学自动机，这里有必要先给出概念，这样才能更好的理解后面的芝士。

1.1 自动机

自动机，在 OI 中一般我们涉及的是有限状态自动机，它拥有有限数量的状态，每个状态代表不同的意义，每个状态可以通过输入自动机，让自动机切换到其他的状态。任意时刻状态机只能处在一个状态。

而有限状态机可以表示为一个有向图：

从图中看出来一个信息学竞赛一共包含 5 个状态：学信竟，学 whk，吃吃饭，睡睡觉，摸摸鱼。每种带有箭头的连线，表示可以从当前状态切换到其他的状态，以及切换的条件。

我们列个表格：

	学信竟	学 whk	吃吃饭	睡睡觉	摸摸鱼
学信竟			去机房		摆烂时间到
学 whk	信竟时间到			回去午睡
吃吃饭	去食堂	去教室
睡睡觉		回教室	被吵醒
摸摸鱼				回家

表格中左侧第一列为当前状态。
表格中上方第一行为切换的下一个状态。
表格中每行从左到右为状态切换的条件(状态 A 能不能切换到状态B)。

举例：

学 whk -> 学信竟：条件（信竟时间到）。
学信竟 -> 摸摸鱼：条件（摸鱼时间到）。
摸摸鱼 -> 睡睡觉：条件（回家）。

几个概念：

状态：当前所处的状态，在当前状态下可以有不同的行为和属性。
转移：状态变更，满足条件是从一个状态转移到另一个状态。
动作：表示在给定时刻进行的活动。
条件：触发一个事件、当一个条件满足触发状态转移切换到另一个状态。

一个自动机，我们应当还有起始状态，在本图中我们的起始状态是 “睡睡觉”。（不准通宵！）

那为啥叫自动呢，是因为只要输入符号和转移规则确定，状态变化是自动的，自动机可以自己通过设定好的路线（即有向图的边权）来进行转移。

而自动机的实质就是：状态集合（点） + 转移规则（边）。

在竞赛中的应用我们有 AC 自动机，后缀自动机，DP 套 DP等。

1.2 Trie 与 AC 自动机

那我们上面提到了自动机，那么，信竟中有哪些我们值得举例的呢？

例如字典树，我们看看字典树的形状，我们借用 OI-Wiki 的图：

那我们回看上面的自动机表示图，你会发现两者十分相似，我们模拟一下 Trie 的过程。

我们把自动机丢在 1 号点，让自动机读入字符串。起始状态在 1 号点，让后我们输入一个字符 a，就转移到 2 号点，让后输入一个字符 b，转移到 6 号点，让后输入一个字符 a，转移到 11 号点。

那么实际上，字典树其实就是一个自动机，通过接受指定字符串集合中的元素来转移，而转移的时候就是利用 Trie 图上的边来进行转移。

而 AC 自动机，是 Trie+Fail 指针，本质上是 Trie 上的自动机。

Trie 不用说我们上面已经提到过了，那么既然 AC 自动机叫自动机，那么 Trie+Fail 这一甜蜜组合一定也能构成自动机吧？其实是的，Fail 指针实际上就是在 Trie 的有向转移图上进行拓展。在单模式匹配中，失败时需要回溯文本指针；而 AC 自动机通过失配指针自动匹配状态，让 Trie 进化为一条永通路，以便避免文本串匹配时一个模式串到结尾了没有地方可走的尴尬。

严格来说，AC自动机是一个带有失败转移的确定性有限状态自动机（DFA），在经典的 Trie 上我们增加了失败状态的优化处理机制。而我们引入失配指针，是为了最小化状态数（避免为所有可能的失败情况显式建边），同时保持高效匹配。而AC自动机的 “自动” 正体现在其能根据预定义的转移规则（包括正常转移和失败转移），无需人工干预地完成多模式匹配。

2. AC 自动机上 DP

2.1 状态设计

我们上面讲自动机当然不是摆烂的，我们需要结合芝士进行讲解。

众所周知，AC 自动机上的 DP，一般来说都是这么设计状态 $f(i,j)$ ，表示长度为 $i$ 的字符串在 AC 自动机上匹配到 $j$ 节点。但是我们为什么这个设计？

动态规划通过将问题分解为子问题，并存储子问题的解（状态）来避免重复计算。关键在于：

状态定义；
状态转移；
边界确定；

而 AC 自动机上 DP，本质就是自动机上的 DP，其本质就是：将问题的约束条件建模为一个自动机，在 DP 状态中增加自动机的状态维度，通过在自动机上逐层推进的转移规则指导 DP 的决策。因为自动机的状态是唯一确定的，通过 AC 自动机的有向转移图，我们就可以方便的进行状态转移，并进行答案统计。

通常来说，自动机上的 DP 我们需要自动机的状态，一般来说为 $f(i,S)$ ，其中 $i$ 是一个确定的顺序，而 $S$ 代表自动机的状态。对应到 AC 自动机上，AC 自动机的状态是一个节点，所以我们定义 $f(i,j)$ ，表示长度为 $i$ 的字符串在 AC 自动机上匹配到 $j$ 节点。

还是来看例题吧：

2.2 例题

USACO12JAN] Video Game G

对输入的模板串建 AC 自动机，设 $f(i,j)$ 表示前 $i$ 个字符，最后一个跑到了 AC 自动机 $j$ 号点的最大答案，我们只需要枚举对于每一个 $f(i,j)$ 下一个是字符是什么，题目中是 A，B，C。转移到下一个节点，让后跳 Fail 指针求答案，对于匹配到一个长度为 $k$ 的模板串，有 $f(i,son[j][k]) = \max(f(i-1,j)+end[son[j][k]]$ 。直接做就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e4+15;
int n,K,f[MN][520];

struct ACAuto{
    int t[MN][3],fail[MN],end[MN],tot;

    void insert(string s){
        int p=0;
        for(auto c:s){
            int k=c-'A';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[p]++;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<3;i++){
            if(t[0][i]) q.push(t[0][i]);
        }  
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<3;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
            end[u]+=end[fail[u]];
        }
    }

}t;


signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        t.insert(s);
    }
    t.build();
    memset(f,-0x3f,sizeof(f));
    for(int i=0;i<=K;i++) f[i][0]=0;
    for(int i=1;i<=K;i++){
        for(int j=0;j<=t.tot;j++){
            for(int k=0;k<3;k++){
                f[i][t.t[j][k]]=max(f[i][t.t[j][k]],f[i-1][j]+t.end[t.t[j][k]]);
            }
        }
    }
    int ans=-0x3f3f3f3f;
    for(int i=0;i<=t.tot;i++) ans=max(ans,f[K][i]);
    cout<<ans;
    return 0;
}

JSOI2007 文本生成器

本部分是反向的计算 DP。

状态还是我们上面所说的， $f(i,j)$ ，表示长度为 $i$ 的字符串在 AC 自动机上匹配到 $j$ 节点。但是题目中还有一个限制：“包含至少一个”，考虑容斥，答案就是整体减去一个模式串都不包含的文本串数。整体是 $26^m$ ，问题转化为求解第二部分。

文本串中不能出现模式串，所以我们要在一个字符串的末尾打标记 $end_{u}$ ，同时如果一个字符串的后缀也是模式串，那么它也不能出现在文本串中，所以我们要让 $end_{u}=end_{fail[u]}$ 。

那么转移方程就是避开模式串进行转移：

void dodp(){
    f[0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=tot;j++){
            for(int k=0;k<26;k++){
                if(!end[ch[j][k]]){
                    f[i+1][ch[j][k]]=(f[i+1][ch[j][k]]+f[i][j])%MOD;
                }
            }
        }
    }
}

那么第二部分答案就是 $\sum\limits_{i=1}^{cnt} f(m,i)$ ，其中 $cnt$ 表示 AC 自动机的点数，那么答案就是：

26^m - \sum\limits_{i=1}^{cnt} f(m,i) \pmod{10007}

直接写：

#include<bits/stdc++.h>
using namespace std;
constexpr int MOD=1e4+7,MN=120,MK=1e5;
int n,m,f[MN][MK];

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}

inline string stread()
{
    char ch = getchar();
    string st1 = "";
    while (!((ch >= 'A') && (ch <= 'Z')))
        ch = getchar();
    while ((ch >= 'A') && (ch <= 'Z'))
        st1 += ch, ch = getchar();
    return st1;
}


struct Acauto{
    int ch[MK][26],tot,fail[MK],end[MK];

    void insert(string s){
        int p=0;
        for(auto c:s){
            if(!ch[p][c-'A']) ch[p][c-'A']=++tot;
            p=ch[p][c-'A'];
        }
        end[p]=1;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(ch[0][i]) q.push(ch[0][i]);
        }
        while(!q.empty()){
            int f=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(ch[f][i]){ 
                    fail[ch[f][i]]=ch[fail[f]][i];
                    q.push(ch[f][i]);
                    end[ch[f][i]]|=end[fail[ch[f][i]]];
                }
                else ch[f][i]=ch[fail[f]][i];
            }
        }
    }

    void dodp(){
        f[0][0]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<=tot;j++){
                for(int k=0;k<26;k++){
                    if(!end[ch[j][k]]){
                        f[i+1][ch[j][k]]=(f[i+1][ch[j][k]]+f[i][j])%MOD;
                    }
                }
            }
        }
    }

}ac;

int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=(ret*a)%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

int main(){
    read(n);
    read(m);
    for(int i=1;i<=n;i++){
        string s;
        s=stread();
        ac.insert(s);
    }
    ac.build();
    ac.dodp();
    int ans=qpow(26,m);
    for(int i=0;i<=ac.tot;i++){
        ans=(ans-f[m][i]+MOD)%MOD;
    }
    cout<<ans;
    return 0;
}

SDOI2014 数数

自动机上 DP 可以与许多不同类型的 DP 结合，因为实质上自动机上 DP 利用的是自动机的转移顺序，所以很灵活可以与许多类型的 DP 结合，这里是数位 DP。

注意到本题就是不让特定的模式数串出现，考虑到一个集合有许多模式数串，考虑 AC 自动机，因为自动机上的 DP 我们是必须要知道自动机跑到哪里了，有一个维度必须设计 $S$ 表示 AC 自动机上的节点（即自动机状态）。本题在数位 DP 只需要关心自动机状态即可，考虑设 $f[pos][st]$ 表示现在从最高位填到第 $pos$ 位，当前 AC 自动机状态节点在 $st$ 。通过记忆化搜索是很容易实现的，注意一下前导零也是算模式串里面的，注意实现细节。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1520,MOD=1e9+7;
int m,a[MN],tot,f[MN][MN];
string n;

struct ACAuto{
    int t[MN][12],tot,fail[MN],end[MN];

    void insert(string s){
        int p=0;
        for(auto c:s){
            int k=c-'0';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[p]=1;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<10;i++){
            if(t[0][i]) q.push(t[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            
            for(int i=0;i<10;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
            end[u]|=end[fail[u]];
        }
    }

}t;

int dfs(int pos,bool lim,bool lead,int st){
    if(t.end[st]) return 0;
    if(!pos) return !lead;
    if(!lim&&!lead&&~f[pos][st]) return f[pos][st];
    int up=lim?a[pos]:9;
    int ret=0;
    for(int i=0;i<=up;i++){
        ret=(ret+dfs(pos-1,lim&&i==up,(lead&&!i),(lead&&!i)?0:t.t[st][i]))%MOD;
    }
    if(!lim&&!lead) f[pos][st]=ret;
    return ret;
}

int solve(){
    memset(f,-1,sizeof(f));
    tot=0;
    for(auto c:n){
        a[++tot]=(int)(c-'0');
    }
    reverse(a+1,a+1+tot);
    return dfs(tot,1,1,0);
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        t.insert(s);
    }
    t.build();
    cout<<solve();
    return 0;
}

CF696D Legen

有的时候，转移过程过大，但是通过借助 AC 自动机状态数有的时候较小，我们可以通过矩阵快速幂来优化 DP 这一过程。

顺便推销自己优质文章：矩阵快速幂优化DP。

有显然的转移，和第一道例题差不太多。设 $f(i,j)$ 表示前 $i$ 个字符，最后一个跑到了 AC 自动机 $j$ 号点的最大答案，有显然的转移方程：

f(i+1,j')=\max(f(i,j)+end[j'])

其中 $j'$ 为当前状态 $j$ 转移后的节点，而 $end[j']$ 表示自动机在节点 $j'$ 上有多少模式串以该节点为结尾的数量。

但是问题在于 $l$ 太大啦！怎么办？观察数据范围，注意到 $n\le 200,\sum\limits |S_{i}|\le 200$ ，也就是说一个模式串的长度是很小的，也就是说 AC 自动机转移的状态数是很小的，但是转移过程是巨大不可接受的，浓烈的矩阵优化味道，考虑矩阵快速幂优化。我们可以把转移图当作在有向图上进行转移，我们把 AC 自动机的图当作邻接矩阵存起来，让后利用广义矩阵乘法矩阵快速幂，接着再给初始状态以其他状态作为结束状态的权值和取个最大值即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=201,INF=1e9;
int n,L,a[MN],ret;

struct Matrix{
    int mat[MN][MN];

    Matrix(int x=-1e9){
        for(int i=0;i<MN;i++){
            for(int j=0;j<MN;j++){
                mat[i][j]=-INF;
            }
        }
        for(int i=0;i<MN;i++){
            mat[i][i]=x;
        }
    }

    Matrix operator *(const Matrix &x)const{
        Matrix ret;
        for(int i=0;i<MN;i++){
            for(int j=0;j<MN;j++){
                for(int k=0;k<MN;k++){
                    ret.mat[i][j]=max(ret.mat[i][j],mat[i][k]+x.mat[k][j]);
                }
            }
        }
        return ret;
    }

}G;

struct ACAuto{
    int t[MN][26],tot,fail[MN],end[MN];

    void insert(string s,int val){
        int p=0;
        for(auto c:s){
            int k=c-'a';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[p]+=val;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(t[0][i]) q.push(t[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
            end[u]+=end[fail[u]];
        }
        for(int i=0;i<=tot;i++){
            for(int j=0;j<26;j++){
                G.mat[i][t[i][j]]=end[t[i][j]];
            }
        }
    }

}t;

Matrix ksm(Matrix a,int b){
    Matrix ret(0);
    while(b){
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}


signed main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        t.insert(s,a[i]);  
    }
    t.build();
    Matrix QwQ=ksm(G,L);
    for(int i=0;i<=t.tot;i++){
        ret=max(ret,QwQ.mat[0][i]);
    }
    cout<<ret;
    return 0;
}

UVA1401 Remeber the Word

来点不一样的，Trie 上 DP，别忘了 Trie 也是一个自动机！

设 $f(i)$ 表示 $i \to len$ 有多少种表示方法，转移如下：

\begin{aligned}f(i) & = \sum\limits f(j+1) & s _{i}\in [i+1,j]\text{ 可以由多个字典拼成} \end{aligned}

利用字典树就可以快速判断，DP 结果为 $f(0)$ 。

HNOI2004 L语言

本题目是状压 DP 的运用用于优化 DP 过程中跳 Fail 的复杂度。

有一个显然的思路就是建 AC 自动机，让后在子殴打凝固剂上对于所有 fail 指针的子串，让后取最大值得到答案，但是这样的复杂度不是线性因为要跳 fail。

根据题目特殊性质，所有单词长度只有 $20$ ？不难考虑到状压，但是我们要状压什么？我们的时间瓶颈在于跳 fail 这一步，我们不妨将其优化到 $O(1)$ ！

我们可以将前 $20$ 位字母所有可能的字串长度存下来，并压缩到状态中，并存于每个字节点中。

那么我们插入和建 fail 可以这么写：

void insert(string s,int id){
    int p=0;
    for(auto c:s){
        int k=c-'a';
        if(!t[p][k]) t[p][k]=++tot;
        p=t[p][k];
    }
    end[p]=id;
}

void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(t[0][i]){
            q.push(t[0][i]);
            dep[t[0][i]]=1;
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        st[u]=st[fail[u]];
        if(end[u]){
            st[u]|=1<<(dep[u]);
        }
        for(int i=0;i<26;i++){
            int v=t[u][i];
            if(v){
                fail[v]=t[fail[u]][i];
                dep[v]=dep[u]+1;
                q.push(v);
            }else t[u][i]=t[fail[u]][i];
        }
    }
}

而查询我们这么写：

int query(string s){
    int p=0,mx=0;
    unsigned now=1;
    for(int i=0;i<s.length();i++){
        int k=s[i]-'a';
        p=t[p][k];
        now<<=1;
        if(st[p]&now) now|=1,mx=i+1; // 若与不为 0 那么长度集交集非空，那就是有匹配串。
    }
    return mx;
}

代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e6+15;
int n,m;

struct ACAuto{
    int t[MN][26],tot,end[MN],dep[MN],fail[MN],st[MN];

    void insert(string s,int id){
        int p=0;
        for(auto c:s){
            int k=c-'a';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[p]=id;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(t[0][i]){
                q.push(t[0][i]);
                dep[t[0][i]]=1;
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            st[u]=st[fail[u]];
            if(end[u]){
                st[u]|=1<<(dep[u]);
            }
            for(int i=0;i<26;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    dep[v]=dep[u]+1;
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
        }
    }

    int query(string s){
        int p=0,mx=0;
        unsigned now=1;
        for(int i=0;i<s.length();i++){
            int k=s[i]-'a';
            p=t[p][k];
            now<<=1;
            if(st[p]&now) now|=1,mx=i+1;
        }
        return mx;
    }

}t;

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

int main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        string s;
        read(s);
        t.insert(s,i);
    }
    t.build();
    for(int i=1;i<=m;i++){
        string s;
        read(s);
        put(t.query(s));
    }
    return 0;
}

3. Fail 树

有的时候，我们的复杂度瓶颈就在于跳 Fail 这一步。

思考一下 AC 自动机的匹配过程：从第一个字符开始，每到达一个节点 $x$ ，就从 $x$ 开始不断跳 fail 到根。期间跳到的节点代表的串都在文本串中出现。

既然我们可以从文本串每一位向上跳 fail 找模式串结尾节点，那么，我们可以倒过来！我们从结尾节点逆着找 fail 找文本串节点！

那么，从结尾节点开始逆着跳 fail，期间跳到的文本串节点个数就是这个模式串在文本串中出现的次数。

而 Fail 树，就是 AC 自动机建立好之后，只留下反向的 Fail 指针作为边，就得到的 Fail 树：

而这颗树是在一个 Trie 的基础上产生的，所以这棵树上的每个点都是一个字符串的前缀，而且每个字符串的每个前缀在这棵树上都对应着一个点。其次，由于 fail 指针，每个点父节点的字符串都是这个点字符串的后缀，并且树上没有更长的它的后缀。也就是说，对于字符串 $s$ ，在 Fail 树上的祖先就是 $s$ 的所有子串。

这是一个 Trick：一个串对应终止节点在 fail 树上到根的这段路径就是他的所有子串。我们后面会提到的。

而对于任意两个节点，它们在 Fail 树上的 LCA 就是它们所共同拥有的子串。

那么怎么优化跳 Fail 呢？只需要将每个属于文本串的终止节点权值设置为 $1$ ，那么节点 $x$ 的子树总权值就是 $x$ 代表的串在文本串中出现的次数。

那怎么快速求呢？这里有一个 Trick：子树的 DFN 序是连续的一个区间。那么我们就可以通过 DFS 序加树状数组来进行实现，接下来我们来看例题：

P2414 [NOI2011] 阿狸的打字机

首先一个很 native 的想法就是把所有串拿出来建 AC 自动机，让后暴力跳 fail 找 $x$ 串的末尾，但是这样时间复杂度是飞起的。

但是，我们在跳 fail 啊，我们是不是可以用上面的思路来求解呢？每次查询从 $y$ 串向上跳到 $x$ 终止节点，而反过来就是往子树跳能达到多少个 $y$ 串的节点，这不就是我们上面所说的吗！我们每次把 $y$ 这个串插入树状数组的时候，只需要对 $y$ 所在子树 $+1$ 即可，对应到 DFN 上就是区间加。这不就是树状数组加差分吗！对于结束的位置打 $-1$ ，其余打 $1$ 。让后就做完了，代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=8e5+15;
struct Query{ int x,y,id; } qry[MN];
int n, siz[MN], dfn[MN], ans[MN],stk[MN], dtot;
string st;
vector<int> ft[MN];

struct BIT {
    int t[MN];
    int lowbit(int x) { return x&-x; }
    int query(int x) {
        int ret=0;
        while(x>0) ret+=t[x], x-=lowbit(x);
        return ret;
    }
    void update(int x, int k) {
        while(x<MN) t[x]+=k, x+=lowbit(x);
    }
} bit;

namespace ACAuto {
    struct Node { int ch[26], fail; } t[MN];
    int tot, g_top, ctot, cut[MN], sta[MN];

    void buildAC(string str) {
        int p = 0;
        g_top = 0;
        for (int i=0; i<str.length(); i++) {
            if (str[i]>='a' && str[i]<='z') {
                int ch = str[i]-'a';
                if (!t[p].ch[ch]) t[p].ch[ch] = ++tot;
                p = t[p].ch[ch];
                sta[++g_top] = p;
            } else if (str[i]=='B') {
                p = sta[--g_top];
            } else {
                cut[++ctot] = p;
            }
        }
    }

    void build() {
        queue<int> q;
        for (int i=0; i<26; i++) {
            if (t[0].ch[i]) {
                q.push(t[0].ch[i]);
                ft[0].push_back(t[0].ch[i]);
            }
        }
        while (!q.empty()) {
            int f = q.front(); q.pop();
            for (int i=0; i<26; i++) {
                int &v = t[f].ch[i];
                if (v) {
                    t[v].fail = t[t[f].fail].ch[i];
                    ft[t[v].fail].push_back(v);
                    q.push(v);
                } else {
                    v = t[t[f].fail].ch[i];
                }
            }
        }
    }
}
using namespace ACAuto;

bool cmp(Query x, Query y) {
    return x.y != y.y ? x.y < y.y : x.id < y.id;
}

void dfs(int u) {
    dfn[u] = ++dtot;
    siz[u] = 1;
    for (int v : ft[u]) {
        dfs(v);
        siz[u] += siz[v];
    }
}

int main() {
    cin >> st;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> qry[i].x >> qry[i].y;
        qry[i].id = i;
    }
    sort(qry+1, qry+n+1, cmp);

    buildAC(st);
    build();
    dfs(0);

    for (int i=1, p=0, top=0, pt=0, up=0; i<=n; i++) {
        while (up < qry[i].y) {
            if (st[pt]>='a' && st[pt]<='z') {
                int ch = st[pt]-'a';
                p = t[p].ch[ch];
                stk[++top] = p;
                bit.update(dfn[p], 1);
            } else if (st[pt]=='B') {
                bit.update(dfn[p], -1);
                p = stk[--top];
            } else {
                up++;
            }
            pt++;
        }
        int node = cut[qry[i].x];
        ans[qry[i].id]=bit.query(dfn[node]+siz[node]-1)- bit.query(dfn[node]-1);
    }

    for (int i=1; i<=n; i++) cout << ans[i] << '\n';
    return 0;
}

CF1437G

用到上面我们的 Trick：一个串对应终止节点在 fail 树上到根的这段路径就是他的所有子串。

那么现在问题转化为单点修改和在 Fail 树上一条链查询权值的最大值，对 Fail 树上进行树链剖分即可，代码如下：

但是有重复串，要用 Multiset 维护每个节点的最大权值。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3e5+1145;
int n,m,pval[MN];
vector<int> adj[MN];
multiset<int> val[MN];

struct ACAuto{
    int t[MN][26],tot,fail[MN],end[MN];

    void insert(string s,int x){
        int p=0;
        for(auto c:s){
            int k=c-'a';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[x]=p;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(t[0][i]) q.push(t[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
        }
        for(int i=1;i<=tot;i++){
            adj[fail[i]].push_back(i); 
        }
    }

}ac;

struct Segment{
#define ls p<<1
#define rs p<<1|1


    struct Node{
        int l,r,val;
    }t[MN<<2];

    void pushup(int p){
        t[p].val=max(t[ls].val,t[rs].val);
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            t[p].val=-1;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int pos,int k){
        if(t[p].l==t[p].r){
            t[p].val=k;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) modify(ls,pos,k);
        else modify(rs,pos,k);
        pushup(p);
    }

    int query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val;
        }
        int mid=(t[p].l+t[p].r)>>1;
        int ret=-1;
        if(mid>=fl) ret=max(ret,query(ls,fl,fr));
        if(mid<fr) ret=max(ret,query(rs,fl,fr));
        return ret;
    }

#undef ls 
#undef rs
}sg;

namespace Tree{
    int id[MN],dtot,siz[MN],dep[MN],fa[MN],hson[MN],htop[MN];

    void dfs1(int u,int pre){
        dep[u]=dep[pre]+1;
        siz[u]=1;
        fa[u]=pre;
        for(auto v:adj[u]){
            if(v==pre) continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(!hson[u]||siz[hson[u]]<siz[v]) hson[u]=v;
        }
    }

    void dfs2(int u,int top){
        htop[u]=top;
        id[u]=++dtot;
        if(!hson[u]) return;
        dfs2(hson[u],top);
        for(auto v:adj[u]){
            if(v==fa[u]||v==hson[u]) continue;
            dfs2(v,v);
        }
    }

    int querychain(int x,int y){
        int ret=-1;
        while(htop[x]!=htop[y]){
            if(dep[htop[x]]<dep[htop[y]]) swap(x,y);
            ret=max(ret,sg.query(1,id[htop[x]],id[x]));
            x=fa[htop[x]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        ret=max(ret,sg.query(1,id[x],id[y]));
        return ret;
    }

}
using namespace Tree;

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        ac.insert(s,i);
    }
    ac.build();
    sg.build(1,1,MN-1);
    dfs1(0,0);
    dfs2(0,0);
    for(int i=1;i<=n;i++){
        sg.modify(1,id[ac.end[i]],0);
        pval[i]=0;
         val[ac.end[i]].insert(0);
    }

    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            val[ac.end[x]].erase(val[ac.end[x]].find(pval[x]));
            pval[x]=y;
            val[ac.end[x]].insert(pval[x]);
            sg.modify(1,id[ac.end[x]],*prev(val[ac.end[x]].end()));
        }else{
            string s;
            cin>>s;
            int p=0,ret=-1;
            for(auto c:s){
                int k=c-'a';
                p=ac.t[p][k];
                ret=max(ret,querychain(0,p));
            }
            cout<<ret<<'\n';
        }
    }
    return 0;
}

P5840 Divljak

首先先建出来 AC 自动机。搞出来 Fail 树。

我们暴力的思路就跳 Fail，将经过的路径的权值都加上 1，让后查询特定的终止节点被访问了多少次即可。那么怎么搬到 Fail 树上呢？我们利用树上差分的思想，首先把将要插入的字符串 $P$ 统计在 Trie 中走过的节点，再按照 DFN 排序，每相邻节点在树上位置加 1，表示多一个串匹配上，但是它们的 LCA 及其祖先显然多加了一次，减去 1 即可。自此，我们可以通过树链剖分加树状数组维护即可：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e6+15;
int n,q,a[MN];
vector<int> adj[MN];

struct BIT{
    int t[MN];

    int lowbit(int x){
        return x&-x;
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

    void modify(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

}bit;

struct ACAuto{
    int t[MN][26],tot=1,fail[MN],end[MN];

    void insert(string s,int id){
        int p=1;
        for(auto c:s){
            int k=c-'a';
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[id]=p;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            t[0][i]=1;
        }
        q.push(1);

        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
        }
    }

}t;

namespace Tree{
    int dfn[MN],dfntot,fa[MN],dep[MN],siz[MN],hson[MN],htop[MN];

    void dfs1(int u,int pre){
        siz[u]=1;
        fa[u]=pre;
        dep[u]=dep[pre]+1;
        for(auto v:adj[u]){
            if(v==pre) continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[hson[u]]<siz[v]) hson[u]=v;
        }
    }

    void dfs2(int u,int top){
        htop[u]=top;
        dfn[u]=++dfntot;
        if(!hson[u]) return;
        dfs2(hson[u],top);
        for(auto v:adj[u]){
            if(v==fa[u]||v==hson[u]) continue;
            dfs2(v,v);
        }
    }

    int lca(int x,int y){
        while(htop[x]!=htop[y]){
            if(dep[htop[x]]<dep[htop[y]]){
                swap(x,y);
            }
            x=fa[htop[x]];
        }
        return dep[x]<dep[y]?x:y;
    }

}using namespace Tree;

bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        t.insert(s,i);
    }
    t.build();
    for(int i=2;i<=t.tot;i++){
        adj[t.fail[i]].push_back(i);
    }
    dfs1(1,0);
    dfs2(1,1);
    cin>>q;

    while(q--){
        int op,x;
        string p;
        cin>>op;
        if(op==1){
            cin>>p;
            int len=p.length(),u=1;
            p=" "+p;
            for(int i=1;i<=len;i++){
                int v=p[i]-'a';
                u=t.t[u][v];
                a[i]=u;
            }
            sort(a+1,a+1+len,cmp);
            for(int i=1;i<=len;i++){
                bit.modify(dfn[a[i]],1);
            }
            for(int i=1;i<len;i++){
                bit.modify(dfn[lca(a[i],a[i+1])],-1);
            }
        }else{
            cin>>x;
            int p=t.end[x];
            cout<<bit.query(dfn[p]+siz[p]-1)-bit.query(dfn[p]-1)<<'\n';
        }
    }
    return 0;
}

P2444 POI 2000病毒

本题即构造一个可行的无限长文本串，使没有任何子串为给出模式串中的一个。

那么，实际上就是我们永远都不会跳到某个病毒代码的终止节点，我们会一直在自动机上跑啊跑，也就是说，若能构造文本串，当且仅当自动机有成环，并且走到环的路径及其环内没有终止节点，DFS 判断即可：

等会这个和 Fail 树有啥关系？其实还是要理解跳 Fail 的本质是在干什么。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e4+15;
int n;
bool vis[MN],inst[MN];

namespace ACAuto{
    struct Node{
        int ch[2];
        int end,fail;
    }t[MN];
    int tot;

    void insert(string s){
        int p=0;
        for(auto c:s){
            int cp=c-48;
            if(!t[p].ch[cp]) t[p].ch[cp]=++tot;
            p=t[p].ch[cp];
        }
        t[p].end=1;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<=1;i++){
            if(t[0].ch[i]) q.push(t[0].ch[i]);
        }
        while(!q.empty()){
            int f=q.front();
            q.pop();
            for(int i=0;i<=1;i++){
                int v=t[f].ch[i];
                if(v){
                    t[v].fail=t[t[f].fail].ch[i];
                    t[v].end|=t[t[t[f].fail].ch[i]].end;
                    q.push(v);
                }else t[f].ch[i]=t[t[f].fail].ch[i];
            }
        }
    }

}using namespace ACAuto;

void dfs(int u){
    if(inst[u]){
        cout<<"TAK";
        exit(0);
    }
    if(vis[u]||t[u].end) return;
    inst[u]=vis[u]=1;
    dfs(t[u].ch[0]);
    dfs(t[u].ch[1]);
    inst[u]=0;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string st;
        cin>>st;
        insert(st);
    }
    build();
    dfs(0);
    cout<<"NIE";
    return 0;
}

4. 数据结构结合

通过数据结构和 AC 自动机的完美，我们就可以通过快速维护某些信息来求解答案。

P3121 Censoring G

多模式串匹配，考虑 AC 自动机，难点在于拼合过程。我们发现，一个字符匹配上之后就会删除，让后接着进行匹配，我们发现，只需要记录某个点在 Trie 图上匹配的位置就可以了，一旦成功匹配，我们只需要跳到这个单词的前一个字符的位置即可。考虑怎么维护，我们可以用栈来维护，删除逐个删除字符，加入一个一个加，时间复杂度是 $O(n)$ 的：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e5+15;
int n,top;
int s1[MN];
char s2[MN];
string s;

namespace ACAuto{
    int tot,trie[MN][26];
    int end[MN],fail[MN];

    void insert(string s){
        int p=0;
        for(auto c:s){
            int k=c-'a';
            if(!trie[p][k]) trie[p][k]=++tot;
            p=trie[p][k];
        }
        end[p]=s.length();
    }

    void build(){
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++){
            if(trie[0][i]) q.push(trie[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(trie[u][i]){
                    fail[trie[u][i]]=trie[fail[u]][i];
                    q.push(trie[u][i]);
                }else trie[u][i]=trie[fail[u]][i];
            }
        }
    }

    void query(string s){
        int p=0;
        for(auto c:s){
            p=trie[p][c-'a'];
            s1[++top]=p;
            s2[top]=c;
            while(end[p]){
                top-=end[p];
                p=top?s1[top]:0;
            }
        }
    }

}


int main(){
    cin>>s>>n;
    for(int i=1;i<=n;i++){
        string awa;
        cin>>awa;
        ACAuto::insert(awa);
    }
    ACAuto::build();
    ACAuto::query(s);
    for(int i=1;i<=top;i++) cout<<s2[i];
    return 0;
}

是不是很水，能不能上一点难度啊！

P5599 文本编辑器（毕业题）

？？？安详的睡去 XD。

没关系我们顺着 Subtask 一步一步来：

Subtask 1-2

AC 自动机板子，14分 get！

Subtask 3

只有一个模式串，要不要 KMP 呢？

但是正解显然不是让我们要用 KMP 啊，可是这里只有一个模式串耶？

我们考虑，一个匹配，当且仅当 $s[i-L+1,i]$ 是完全相同的，其中 $L$ 为模式串的长度。我们不妨考虑设 $f(i)$ 表示 $s[i-L+1,i]$ 是否完全匹配，那么查询就是查 $\sum\limits_{k \in [l+len-1,r]} f_{k}$ ，这是区间和，可以上线段树耶。

但是修改怎么办，我们注意到，修改实质上是一个循环，一次修改只会影响 $[l,r+L)$ （有循环截止部分），而我们的 $f(i)$ 只需要判断出没出现过即可，而 $f(i)$ 显然会有一个长度为 $|t|$ 的循环节，而且一定在经过 $L$ 个字符后出现，考虑对循环节之前的地方暴力，中间部分通过线段树打加法标记即可。

但是区间右端点在截止的时候也会修改，考虑把区间 $(r,r+L)$ 的信息暴力修改就可以了，13 分 get！

Subtask 4

没有修改！那我们就不用关心难受的循环节了哈哈哈。

现在问题转化为如何快速求出贡献之和，我们当然要建立起 AC 自动机，但是怎么维护区间呢？

我们考虑设 $f(i)$ 表示 AC 自动机上匹配 $s[1\to i]$ ，的时候，到达的点 $u$ 在 fail 树上子树中有多少终止节点。

不难发现一个对答案有贡献的字符串长度一定 $\le L$ ，考虑对于一个询问 $[l,r]$ ，我们暴力求出 $s[l \to l+L-1]$ 所有字串对答案贡献，让后查询 $f$ 在区间 $[l+L,r]$ 的区间和就可以了。

让后就不会了啊啊啊啊啊啊。

Subtask 5,6,7,114514

这部分参考了s_r_f 的题解。

其实答案就是 $\sum\limits f(i)+g(l,l+L-1)$ ，其中 $g(l,r)$ 表示 $s[l \to r]$ 所有字串对答案的贡献，第二个很好求之前我们讲过，现在问题如何快速维护第一个。

每次区间修改的话必然会有循环节，但是我们只维护 $f$ 是求不出来循环节的，我们考虑我们要知道什么信息才能维护循环节，通过 Sub 3 我们发现，暴力修改完 $[l,l+L-1]$ 之后需要知道匹配到 $s[1\to l+L-1]$ 到 AC 自动机上的节点，也就是说，我们需要维护 $u$ 。

我们考虑在线段树的节点维护两个信息：

$u$ 表示匹配 $s[1\to r]$ 时到了 AC 自动机哪个节点。
$c$ 表示区间 $\sum\limits f(i)$ 。

让后我们对于叶子节点我们还需要知道这个点是什么字符，这样方便我取维护 $u,c$ 。

对于一次查询，我们只需要 $[l,l+L)$ 暴力， $[l+L,r]$ 暴力查 $c$ 。

怎么修改，首先前面 $l+L$ 的部分还是暴力修改，让后我们查询 $[l+L-1,l+L-1]$ 这个叶子节点的 $u$ 来求循环节，让后对 $[l+L,r]$ 进行区间修改，最后在对 $[r+1,r+L]$ 所有的 $u$ 暴力修改以下即可。

没了？没了！（一脸震惊 Orz）

复杂度 $O(62 \times \sum\limits |s_{i}|+q\times (\log n +L))$

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15,L=55;
int n,m,q,id,f[MN],len[MN],sum[MN];
string a,qry[MN];
vector<int> pre[MN];
unordered_map<char,int> mp;

struct ACAuto{
    int t[MN][62],fail[MN],end[MN],tot;

    void insert(string s){
        int p=0;
        for(auto c:s){
            int k=mp[c];
            if(!t[p][k]) t[p][k]=++tot;
            p=t[p][k];
        }
        end[p]++;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<62;i++){
            if(t[0][i]) q.push(t[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            end[u]+=end[fail[u]];
            for(int i=0;i<62;i++){
                int v=t[u][i];
                if(v){
                    fail[v]=t[fail[u]][i];
                    q.push(v);
                }else t[u][i]=t[fail[u]][i];
            }
        }
    }

    void getf(){
        int p=0;
        for(int i=1;i<=n;i++){
            p=t[p][mp[a[i-1]]];
            f[i]=end[p];
        }
    }
    
}ac;

struct Segment{
    #define ls p<<1
    #define rs p<<1|1

    struct Lazytag{
        int id,hd;
    };
    struct Node{
        int l,r,val;
        Lazytag tag;
    }t[MN<<2];
    int lpos;
    string tmp;

    void pushup(int p){
        t[p].val=t[ls].val+t[rs].val;
    }

    void dotag(int p,int id,int hd){
        t[p].tag={id,hd};
        int bef=t[p].l-hd,lid=(t[p].r-bef)%len[id],rid=(t[p].r-bef)/len[id];
        if(rid==0){
            t[p].val=pre[id][lid]-(hd?pre[id][hd-1]:0);
        }else t[p].val=pre[id][lid]+rid*sum[id]-(hd?pre[id][hd-1]:0);
    }

    void pushdown(int p){
        if(t[p].tag.id){
            int id=t[p].tag.id,hd=t[p].tag.hd,val=(hd+(t[ls].r-t[ls].l+1))%len[id];
            dotag(ls,id,hd);
            dotag(rs,id,val);
            t[p].tag.id=0;
        }
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            t[p].val=f[l];
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modifyt(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            dotag(p,id,(t[p].l-lpos)%len[id]);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modifyt(ls,fl,fr);
        if(mid<fr) modifyt(rs,fl,fr);
        pushup(p);
    }

    void modifyc(int p,int fl,int fr,bool tg){
        if(fl>fr) return;
        if(t[p].l==t[p].r){
            t[p].val=f[t[p].l];
            if(tg){
                t[p].tag={id,(t[p].l-lpos)%len[id]};
            }
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modifyc(ls,fl,fr,tg);
        if(mid<fr) modifyc(rs,fl,fr,tg);
        pushup(p);
    }

    void modify(int p,int fl,int fr){
        if(fl>fr) return;
        if(t[p].l==t[p].r){
            if(t[p].tag.id){
                tmp+=qry[t[p].tag.id][t[p].tag.hd];
            }else tmp+=a[t[p].l-1];
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modify(ls,fl,fr);
        if(mid<fr) modify(rs,fl,fr);
        pushup(p);
    }

    int query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        int ret=0;
        if(mid>=fl) ret+=query(ls,fl,fr);
        if(mid<fr) ret+=query(rs,fl,fr);
        return ret;
    }

    #undef ls
    #undef rs
}sg;

void initmp(){
	for(int i='A';i<='Z';i++)mp[i]=i-'A';
	for(int i='a';i<='z';i++)mp[i]=26+(i-'a');
	for(int i='0';i<='9';i++)mp[i]=52+(i-'0');
}

signed main(){
    initmp();
    cin>>n>>m>>q>>a;
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        ac.insert(s);
    }
    ac.build();
    ac.getf();
    sg.build(1,1,n);
    while(q--){
        int op,l,r,ls;
        cin>>op>>l>>r;
        ls=r-l+1;
        sg.lpos=l;
        if(op==1){
            int rpos=min(r,l+L),ret=0,p=0;
            sg.tmp="";
            sg.modify(1,l,rpos);
            for(int i=l;i<=rpos;i++){
                p=ac.t[p][mp[sg.tmp[i-l]]];
                ret+=ac.end[p];
            }
            cout<<ret+sg.query(1,rpos+1,r)<<'\n';
        }else{
            string st;
            cin>>st;
            len[++id]=st.size();
            pre[id].resize(len[id]);
            int lpos=max(1ll,l-L+1),rpos=min(n,r+L-1);
            int p=0;
            if(ls<=L*2+len[id]*2){
                sg.tmp="";
                sg.modify(1,lpos,rpos);
                for(int i=lpos;i<=rpos;i++){
                    char ch=(i<l||i>r?sg.tmp[i-lpos]:st[(i-l)%len[id]]);
                    p=ac.t[p][mp[ch]];
                    if(i>=l) f[i]=ac.end[p];
                }
                sg.modifyc(1,l,r,1);
                sg.modifyc(1,r+1,rpos,0);
            }else{
                int led=l+L-1,red=r-L+1;
                while((led-l)%len[id]) led++;
                sg.tmp="";
                sg.modify(1,lpos,l-1);
                for(int i=lpos;i<led+len[id];i++){
                    char ch=(i<l?sg.tmp[i-lpos]:st[(i-l)%len[id]]);
                    p=ac.t[p][mp[ch]];
                    if(i>=l){
                        if(i<led) f[i]=ac.end[p];
                        else pre[id][i-led]=(i>led?pre[id][i-led-1]:0)+ac.end[p];
                    }
                }
                sum[id]=pre[id][len[id]-1];
                sg.modifyc(1,l,led-1,1);
                sg.modifyt(1,led,r);

                sg.tmp="";
                sg.modify(1,r+1,rpos);
                for(int i=red;i<=rpos;i++){
                    char ch=(i>r?sg.tmp[i-r-1]:st[(i-l)%len[id]]);
                    p=ac.t[p][mp[ch]];
                    if(i>r){
                        f[i]=ac.end[p];
                    }
                }
                sg.modifyc(1,r+1,rpos,0);
            }
            qry[id]=st;
        }
    }
    return 0;
}