存代码

然后国家集训队2017年的论文

在后面插入的

IL void Extend(RG int pos, RG int c){    RG int p = last;    while(s[pos - len[p] - 1] != s[pos]) p = fa[p];    if(!son[c][p]){        RG int np = ++tot, q = fa[p];        while(s[pos - len[q] - 1] != s[pos]) q = fa[q];        len[np] = len[p] + 2, fa[np] = son[c][q];        son[c][p] = np;    }    last = son[c][p], ++size[last];}

支持前后插入，维护最长回文前缀和最长回文后缀

前缀的\(fail\)和后缀的\(fail\)相同，因为回文串的对称性

题目

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(1e5 + 5);int n, tot, prel, sufl, son[26][maxn], len[maxn], deep[maxn], fa[maxn], l, r;ll ans;char s[maxn << 1];IL void Init(){    for(RG int i = l; i <= r; ++i) s[i] = 'z' + 1;    for(RG int i = 0; i <= tot; ++i){        len[i] = deep[i] = fa[i] = 0;        for(RG int j = 0; j < 26; ++j) son[j][i] = 0;    }    prel = sufl = 0, tot = 1, fa[1] = fa[0] = 1, len[1] = -1;}IL void Extend(RG int pos, RG int c, RG int &last, RG int op){    RG int p = last;    while(s[pos - op * (len[p] + 1)] != s[pos]) p = fa[p];    if(!son[c][p]){        RG int np = ++tot, q = fa[p];        while(s[pos - op * (len[q] + 1)] != s[pos]) q = fa[q];        len[np] = len[p] + 2, fa[np] = son[c][q];        son[c][p] = np;    }    last = son[c][p], deep[last] = deep[fa[last]] + 1, ans += deep[last];    if(len[last] == r - l + 1) prel = sufl = last;}int main(){    while(scanf("%d", &n) != EOF){        Init(), l = 1e5, r = l - 1, ans = 0;        for(RG int i = 1; i <= n; ++i){            RG int op = Input();            if(op <= 2){                RG char c; scanf(" %c", &c);                if(op == 1) s[--l] = c, Extend(l, c - 'a', prel, -1);                else s[++r] = c, Extend(r, c - 'a', sufl, 1);            }            else printf("%lld\n", op == 3 ? tot - 1 : ans);        }    }    return 0;}
    

求回文子串个数

如果是本质不同的，即就是回文树的点数减去两个根

否则就是 \(fail\) 树上的 \(deep\) 和也就是 \(size\) 和这两个显然相等

一个点的 \(deep\) 表示以这个点包含的端点集合为右端点的回文串的个数

一个点的 \(size\) 表示这个点表示的回文串出现的端点集合大小

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(1005);int fa[maxn], num[maxn], len[maxn], son[26][maxn], ans, n, tot, last;char s[maxn];IL void Extend(RG int pos, RG int c){    RG int p = last;    while(s[pos - len[p] - 1] != s[pos]) p = fa[p];    if(!son[c][p]){        RG int q = fa[p], np = ++tot;        while(s[pos - len[q] - 1] != s[pos]) q = fa[q];        fa[np] = son[c][q];        son[c][p] = np, len[np] = len[p] + 2;    }    last = son[c][p], ++num[last];}int main(){    scanf(" %s", s + 1), n = strlen(s + 1);    tot = 1, len[1] = -1, fa[0] = fa[1] = 1;    for(RG int i = 1; i <= n; ++i) Extend(i, s[i] - 'a');    for(RG int i = tot; i; --i) num[fa[i]] += num[i];    for(RG int i = 2; i <= tot; ++i) ans += num[i];    printf("%d\n", ans);    return 0;}
    

字符集大时\(map\)

卡空间时邻接表