PAM 模板

回文串问题。

查看代码

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
char str[N];
int n, cnt;
struct Node { int p, len, nxt[26]; } tr[N];
int get (int x, int t)
{
    while (str[t - 1 - tr[x].len] != str[t]) x = tr[x].p;
    return x;
}
void build()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    tr[0].p = 1, tr[1].len = -1;
    cnt = 2;
    for (int i = 1, p = 0; i <= n; ++i)
    {
        int c = str[i] - 'A';
        p = get(p, i);
        if (!tr[p].nxt[c])
        {
            int q = cnt++;
            tr[q].len = tr[p].len + 2;
            tr[q].p = tr[get(tr[p].p, i)].nxt[c];
            tr[p].nxt[c] = q;
        }
        p = tr[p].nxt[c];
    }
}