2018-team4-modules-回文自动机

从 Trac 迁移的文章

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

原文章内容如下：

{{{
struct Node{
    int nx[2];
    int len,fail,siz;
}T[maxn];
int nodecnt,last,s[maxn],len;
inline void init(){
    T[last = nodecnt = 0].fail = 1;
    T[++nodecnt].len = -1;
}
inline void insert(int c){
    s[++len] = c;int cur,p,x;
    for(p = last;p != 1 && (s[len-T[p].len-1] == s[len] || (len-T[p].len-1 == 0));p = T[p].fail);
    if((s[len-T[p].len-1] == s[len] || (len-T[p].len-1 == 0))){last = 0;return;}
    if(T[p].nx[c] == 0){
        T[cur = ++ nodecnt].len = T[p].len + 2;
        for(x = T[p].fail;x != 1 && (s[len-T[x].len-1] == s[len] || (len-T[p].len-1 == 0));x = T[x].fail);
        if(s[len-T[x].len-1] == s[len]) T[cur].fail = 0;
        else T[cur].fail = T[x].nx[c];
        T[p].nx[c] = cur;
    }T[last = T[p].nx[c]].siz ++ ;
}
}}}

struct Node{
    int nx[2];
    int len,fail,siz;
}T[maxn];
int nodecnt,last,s[maxn],len;
inline void init(){
    T[last = nodecnt = 0].fail = 1;
    T[++nodecnt].len = -1;
}
inline void insert(int c){
    s[++len] = c;int cur,p,x;
    for(p = last;p != 1 && (s[len-T[p].len-1] == s[len] || (len-T[p].len-1 == 0));p = T[p].fail);
    if((s[len-T[p].len-1] == s[len] || (len-T[p].len-1 == 0))){last = 0;return;}
    if(T[p].nx[c] == 0){
        T[cur = ++ nodecnt].len = T[p].len + 2;
        for(x = T[p].fail;x != 1 && (s[len-T[x].len-1] == s[len] || (len-T[p].len-1 == 0));x = T[x].fail);
        if(s[len-T[x].len-1] == s[len]) T[cur].fail = 0;
        else T[cur].fail = T[x].nx[c];
        T[p].nx[c] = cur;
    }T[last = T[p].nx[c]].siz ++ ;
}