后缀自动机

最最详细的解析

基础学习

简洁明了的讲解

小小总结

1. 总状态数不超过 $2n-1$2n−1（包括初始状态）。
2. 统计每个 $endpos$endpos等价类出现位置数量时，要按长度从长到短的计算 $cnt$cnt。那为什么一定要从长到短呢？（比如回文自动机就直接是按照节点编号从大到小计算 $cnt$cnt）罪魁祸首就是复制得到的 $nq$nq，因为它的节点编号比较大，却又要插入到节点编号比它小的 $q$q的头上（作为其父节点），这样就导致若按节点编号计算 $cnt$cnt，会导致某些节点入度还未减到 $0$0就开始更新它的父节点了。
3. 将 $q$q复制一份得到 $nq$nq后，原先的 $q$q就等效于被孤立了，用 $nq$nq去代替它的所有角色（初始的 $cnt$cnt以及第一次的 $endpos$endpos值不能转移给 $nq$nq，因为它们现在是父子关系）。
4. 按长度排序时采用计数排序方便（用于得到第i短的状态 $a\left[i\right]$a[i]）。
5. 遇到多组数据时别忘了初始化 $last$last和 $sz$sz，都为 $1$1。

先记录一个板子

注意：源点(空串)下标为1

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int ch[maxn*2][26], len[maxn*2], fa[maxn*2];
int last=1, tot=1;

void add(int c) {
    int p=last, np=last=++tot;
    len[np]=len[p]+1;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++tot; len[nq]=len[p]+1;
            fa[nq]=fa[q], fa[q]=fa[np]=nq;
            memcpy(ch[nq],ch[q],104);
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

int main() {
    //ios::sync_with_stdio(false);
    scanf("%s", s);
    for(int i=0; s[i]; ++i) add(s[i]-'a');
}