Rockdu's Blog

Description

After finishing his homework, our problem setter Federmann decided to kill time by hanging
around online. He found a cool chat room that discusses competitive programming. Federmann
has already joined lot of such chat rooms, but this one is special. Once he entered the
chat room, he noticed that there is an announcement saying “We forbid off-topic messages!”.
Federmann thinks that’s quite unusual, he decided to sit down and join the talk. After watching
people discussing different programming challenges for a while, he found an interesting
message saying “No, Federmann won’t prepare another problem about strings this year.”
“Oh, why do you guys think about that?” Federmann smiled. “Don’t they know I have
an Edward number2 of 3?”
He then thought about something about palindrome, given two strings A and B, what
is the number of their common palindrome substrings? The amount of common palindrome
substrings between two strings is defined as the number of quadruple (p, q, s, t), which satisfies
that:
1. 1 ≤ p, q ≤ length(A), 1 ≤ s, t ≤ length(B), p ≤ q and s ≤ t. Here length(A) means the
length of string A.
2. Ap..q = Bs..t
3. Ap..q is palindrome. (palindrome string is the string that reads the same forward or
backward)
For example, (1, 3, 1, 3) and (1, 3, 3, 5) are both considered as a valid common palindrome
substring between aba and ababa.
Federmann is excited about his new task, and he is just too lazy to write solutions, help
him.

Input

The first line of the input gives the number of test cases, T. T test cases follow. For each
test case, the first line contains a string A and the second line contains a string B. The length
of A, B will not exceed 200000.
It is guaranteed the input file will be smaller than 8 MB.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case
number (starting from 1) and y is the number of common palindrome substrings of A and B.

题目大意：统计公共回文串的个数，不难想到回文自动机。我们对一个串建立自动机，把另一个串拿上去跑，一边跑先一边更新初步的出现次数，然后拓扑序向上（fail指针）推一遍（类似回文自动机cnt数组的建立），这个时候我们用ans累加 出现次数*len 就好了（所有公共回文串）。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 5;
char s[maxn], word[maxn];

namespace PAM {
	char * s;
	int trie[maxn][26], sum[maxn], fail[maxn], len[maxn], exd[maxn];
	int cnt, pos, last;
	void init(char * str) {
		memset(sum, 0, sizeof(sum));
		memset(exd, 0, sizeof(exd));
		memset(trie, 0, sizeof(trie));
		memset(fail, 0, sizeof(fail));
		memset(len, 0, sizeof(len));
		cnt = 1, pos = last = 0, s = str;
		fail[0] = 1, len[0] = 0, len[1] = -1;
	}
	int getfail(int p) {
		while(s[pos - len[p] - 1] != s[pos])
			p = fail[p];
		return p;
	}
	void add(int x) {
		int id = s[x] - 'a';
		int p = getfail(last);
		if(!trie[p][id]) {
			int now = ++cnt;
			fail[now] = trie[getfail(fail[p])][id];
			trie[p][id] = now;
			len[now] = len[p] + 2;
		}
		last = trie[p][id];
		++sum[last];
	}
	void push_up() {
		for(register int i = cnt; i >= 0; --i)
			sum[fail[i]] += sum[i];
	}
	long long push_exd() {
		long long ans = 0;
		for(register int i = cnt; i >= 2; --i)
			exd[fail[i]] += exd[i], ans += 1LL * exd[i] * sum[i];
		return ans;
	}
	void create() {
		int sl = strlen(s);
		for(register int i = 0; i < sl; ++i)
			pos = i, add(i);
		push_up();
	}
	long long work(char * w) {
		int sl = strlen(w), now = 1;
		for(register int i = 0; i < sl; ++i) {
			int id = w[i] - 'a';
			if(trie[now][id] && i - len[now] - 1 >= 0 && w[i - len[now] - 1] == w[i]) {
				now = trie[now][id], ++exd[now];
			}else {
				int p = now;
				while(p != 1 && (!trie[p][id] || i - len[p] - 1 < 0 || w[i - len[p] - 1] != w[i]))
					p = fail[p];
				if(trie[p][id]) {
					now = trie[p][id];
					++exd[now];
				} else now = 1;
			}
		}
		return push_exd();
	}
}

int t;
int main() {
	scanf("%d", &t);
	for(register int i = 1; i <= t; ++i) {
		scanf("%s", s);
		PAM::init(s);
		PAM::create();
		scanf("%s", word);
		printf("Case #%d: %I64d\n", i, PAM::work(word));
	}
	return 0;
}