2018-team4-modules-后缀自动机

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Node{
    int len,fa;
    map<int,int>nx;
}T[maxn<<2];
int last,nodecnt;
inline void init(){
    last = nodecnt = 0;
    T[0].len = 0;T[0].fa = -1;
}
void insert(int c){
    int cur = ++nodecnt,p;
    T[cur].len = T[last].len + 1;
    for(p=last;p!=-1 && !T[p].nx.count(c);p = T[p].fa)
        T[p].nx[c] = cur;
    if(p == -1) T[cur].fa = 0;
    else{
        int q = T[p].nx[c];
        if(T[q].len == T[p].len + 1) T[cur].fa = q;
        else{
            int co = ++ nodecnt;
            T[co] = T[q];T[co].len = T[p].len+1;
            for(;p!=-1 && T[p].nx[c] == q;p = T[p].fa)
                T[p].nx[c] = co;
            T[q].fa = T[cur].fa = co;
        }
    }last = cur;
}
}}}

struct Node{
    int len,fa;
    map<int,int>nx;
}T[maxn<<2];
int last,nodecnt;
inline void init(){
    last = nodecnt = 0;
    T[0].len = 0;T[0].fa = -1;
}
void insert(int c){
    int cur = ++nodecnt,p;
    T[cur].len = T[last].len + 1;
    for(p=last;p!=-1 && !T[p].nx.count(c);p = T[p].fa)
        T[p].nx[c] = cur;
    if(p == -1) T[cur].fa = 0;
    else{
        int q = T[p].nx[c];
        if(T[q].len == T[p].len + 1) T[cur].fa = q;
        else{
            int co = ++ nodecnt;
            T[co] = T[q];T[co].len = T[p].len+1;
            for(;p!=-1 && T[p].nx[c] == q;p = T[p].fa)
                T[p].nx[c] = co;
            T[q].fa = T[cur].fa = co;
        }
    }last = cur;
}