后缀自动机（SAM）+广义后缀自动机（GSA）

 

经过一顿操作之后竟然疑似没退役0 0

你是XCPC选手吗？我觉得我是！

稍微补一点之前丢给队友的知识吧，除了数论以外都可以看看，为Dhaka和新队伍做点准备...

不错的零基础教程见 IO WIKI - 后缀自动机，这篇就从自己的角度总结一下吧，感觉思路总是和别人不一样...尽量用我比较能接受的语言和逻辑重新组织一遍。

注意：在本文中，字符串的下标从1开始。

目前的 SAM 模板：

const int N=100005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map<char,int> nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;