Victor and String[Bestcoder #52 1004](回文树)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 400000;
struct Plalindrome_Tree{
    int go[26], len, fail;
    ll fail_len;
}pt[N];
int pre, suf, tot;
ll ans;
int q;
int l, r;
char s[N];
void init() {
    memset(s, -1, sizeof(s));
    memset(pt, 0, sizeof(pt));
    tot = ans = 0;
    pre = suf = 0;
    l = 200000;
    r = 199999;
}
void build() {
    pt[++tot].len = -1;
    pt[0].fail = pt[1].fail = 1;
    pt[0].fail_len = 2;
    pt[1].fail_len = 1;
}
void add_back(int c) {
    int p = suf;
    while (s[r - pt[p].len - 1] != s[r]) p = pt[p].fail;
    if (!pt[p].go[c]) {
        int v = ++tot, k = pt[p].fail;
        pt[v].len = pt[p].len + 2;
        while (s[r - pt[k].len - 1] != s[r]) k = pt[k].fail;
        pt[v].fail = pt[k].go[c];
        pt[v].fail_len = pt[pt[k].go[c]].fail_len + 1;
        pt[p].go[c] = v;
    }
    suf = pt[p].go[c];
}
void add_front(int c) {
    int p = pre;
    while (s[l + pt[p].len + 1] != s[l]) p = pt[p].fail;
    if (!pt[p].go[c]) {
        int v = ++tot, k = pt[p].fail;
        pt[v].len = pt[p].len + 2;
        while (s[l + pt[k].len + 1] != s[l]) k = pt[k].fail;
        pt[v].fail = pt[k].go[c];
        pt[v].fail_len = pt[pt[k].go[c]].fail_len + 1;
        pt[p].go[c] = v;
    }
    pre = pt[p].go[c];
}
int main() {
    while (cin >> q) {
        init();
        build();
        while (q--) {
            int opt;
            char ch;
            cin >> opt;
            switch (opt) {
                case 1:
                    cin >> ch;
                    s[--l] = ch;
                    add_front(ch - ‘a‘);
                    ans += pt[pre].fail_len - 2;
                    if (pt[pre].len == r - l + 1) suf = pre;
                    break;
                case 2:
                    cin >> ch;
                    s[++r] = ch;
                    add_back(ch - ‘a‘);
                    ans += pt[suf].fail_len - 2;
                    if (pt[suf].len == r - l + 1) pre = suf;
                    break;
                case 3:
                    cout << tot - 1;
                    puts("");
                    break;
                case 4:
                    cout << ans;
                    puts("");
                    break;
                default:
                    puts("Wrong Input");
                    break;
            }
        }

    }
    return 0;
}