题目链接：传送门

Description

有n种操作，开始给你一个空串，给你4中操作 1 c 在字符串的首部添加字符c 2 c 在字符串的尾部添加字符c 3 询问字符中的本质不同的回文串的个数 4 询问字符串中回文串的个数

Solution

回文自动机的last(或now)搞两个记录即可，其他都是常规操作 只是有些细节要注意一下

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 300000 + 100;

int S[Maxn];
int N, cnt;
LL sum;

struct tree
{
    int cnt, ch[30], len, fail;
};

namespace PAM
{
    tree Tree[Maxn];
    int root0, root1;
    int last[2];
    int l, r;

    inline void init ()
    {
        memset(Tree, 0, sizeof Tree);
        memset(S, -1, sizeof S);
        cnt = -1;
        sum = 0;
        last[0] = last[1] = 1;
        l = Maxn / 2;
        r = l - 1;
        root0 = ++cnt, root1 = ++cnt;
        Tree[root0].fail = root1; Tree[root1].fail = root1;
        Tree[root0].len = 0; Tree[root1].len = -1;
    }

    inline int get_fail (int now, int type)
    {
        if (type) while (S[r - Tree[now].len - 1] != S[r]) now = Tree[now].fail;
        else while (S[l + Tree[now].len + 1] != S[l]) now = Tree[now].fail;
        return now;
    }

    inline void add (int c, int type)
    {
        if (type) S[++r] = c;
        else S[--l] = c;
        int now = get_fail(last[type], type);
        if (!Tree[now].ch[c])
        {
            int x = ++cnt;
            Tree[x].len = Tree[now].len + 2;
            Tree[x].fail = Tree[get_fail(Tree[now].fail, type)].ch[c];
            Tree[x].cnt = Tree[Tree[x].fail].cnt + 1;
            Tree[now].ch[c] = x;
        }
        now = Tree[now].ch[c];
        sum += (LL)Tree[now].cnt;
        last[type] = now;
        if (Tree[now].len == r - l + 1)
            last[type ^ 1] = now;
    }
}

inline char safe_getchar()
{
    char ch = getchar();
    while (ch < 'a' || ch > 'z') ch = getchar();
    return ch;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif

    while (~scanf("%d", &N))
    {
        PAM :: init();
        while (N--)
        {
            int type;
            char c;
            scanf("%d", &type);
            if (type <= 2)
            {
                c = safe_getchar();
                PAM :: add(c - 'a' + 1, type - 1);
            }
            else if (type == 3)
                printf("%d\n", cnt - 1);
            else printf("%lld\n", sum);
        }
    }
    return 0;
}