11月10日, 2016 2,372 views次
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; }