Gym 100548G / UVALive 7041 – The Problem to Slow Down You [回文自动机]

Link

http://codeforces.com/gym/100548/attachments

Mean

给你两个字符串s1和s2，求有多少个四元组(a, b, x, y)使得s1[a:b]==s2[x:y]且s1[a:b]为回文串。两串长度最长均为2e5.

Analysis

比赛时用后缀数组+Manacher+RMQ+主席树瞎凑…最后还是没搞出来…

这题用回文自动机（回文树）就是一个水题了，刚学会这个算法…下面套模板…

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int maxn = 204800;
int kase, N;
char A[maxn], B[maxn];

struct PalindromicTree {

    static const int MAXN = maxn * 2, sigma_size = 26;

    int next[MAXN][sigma_size];
    int fail[MAXN];
    int cnt[2][MAXN];
    int len[MAXN];
    int S[MAXN];
    int last;
    int n;
    int p;

    int newNode(int l) {
        memset(next[p], 0, sizeof(next[p]));
        cnt[0][p] = cnt[1][p] = 0;
        len[p] = l;
        return p++;
    }

    void init() {
        p = 0;
        newNode(0);
        newNode(-1);
        last = n = 0;
        S[0] = -1;
        fail[0] = 1;
    }

    int getFail(int x) {
        while (S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }

    void count(int id) {
        for (int i = p - 1; i >= 0; --i)
            cnt[id][fail[i]] += cnt[id][i];
    }

    void add(int c, int id) {
        c -= 'a';
        S[++n] = c;
        int cur = getFail(last);
        if (!next[cur]) {
            int now = newNode(len[cur] + 2);
            fail[now] = next[getFail(fail[cur])];
            next[cur] = now;
        }
        last = next[cur];
        cnt[id][last]++;
    }
}tree;


int main() {
    scanf("%d", &N);
    while(N--) {
        scanf("%s%s", A, B);
        tree.init();
        for(int i = 0; A[i]; ++i) tree.add(A[i], 0);
        tree.last = tree.n = 0; tree.fail[0] = 1;
        for(int i = 0; B[i]; ++i) tree.add(B[i], 1);
        tree.count(0); tree.count(1);
        ll sum = 0;
        for(int i = tree.p - 1; i >= 2; --i) {
            sum += (ll)tree.cnt[0][i] * tree.cnt[1][i];
        }
        printf("Case #%d: %I64d\n", ++kase, sum);
    }
    return 0;
}