题目链接：https://vjudge.net/problem/POJ-3376
| Time Limit: 10000MS | Memory Limit: 262144K | |
| Total Submissions: 4244 | Accepted: 796 | |
| Case Time Limit: 2000MS | ||
Description
A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.
Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.
Input
The first line of input file contains the number of strings n. The following n lines describe each string:
The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet.
You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.
Output
Print out only one integer, the number of palindromes.
Sample Input
3
1 a
2 ab
2 ba
Sample Output
5
Hint
aa aba aba abba baab
Source
题解：
可知：如果两字符串拼接起来能够形成回文串，那么短串的逆串是长串的前缀。
根据上述结论，我们可以：
1.利用扩展KMP算法求出每个字符串的后缀是否为回文串，以及每个字符串的逆串的后缀是否为回文串。
2.将每个字符串插入到Trie树中，并且Trie树的结点需要维护两个信息：当前结点的字符串数，以及往下有多少个回文串后缀。
3.用每个字符串的逆串去Trie树中查找。有两种情况：当前串作为长串，以及当前串作为短串。详情请看代码。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps = 1e-;
const int INF = 2e9;
const LL LNF = 9e18;
const int MAXN = 2e6+; char str[MAXN], res[MAXN];
int beg[MAXN], len[MAXN], ispal[][MAXN];
int Next[MAXN], exd[MAXN]; struct Node
{
int strnum;
int palnum;
int nxt[];
};
Node node[MAXN];
int tot, root; int newnode()
{
node[tot].strnum = ;
node[tot].palnum = ;
memset(node[tot].nxt, -, sizeof(node[tot].nxt));
tot++;
return tot-;
} void pre_EXKMP(char x[], int m)
{
Next[] = m;
int j = ;
while(+j<m && x[+j]==x[+j]) j++;
Next[] = j;
int k = ;
for(int i = ; i<m; i++)
{
int p = Next[k]+k-;
int L = Next[i-k];
if(i+L<=p) Next[i] = L;
else
{
j = max(, p-i+);
while(i+j<m && x[i+j]==x[+j]) j++;
Next[i] = j;
k = i;
}
}
} void EXKMP(char x[], int m, char y[], int n, int _L, int type)
{
pre_EXKMP(x, m);
int j = ;
while(j<n && j<m && x[j]==y[j]) j++;
exd[] = j;
int k = ;
for(int i = ; i<n; i++)
{
int p = exd[k]+k-;
int L = Next[i-k];
if(i+L<=p) exd[i] = L;
else
{
j = max(,p-i+);
while(i+j<n && j<m && y[i+j]==x[+j]) j++;
exd[i] = j;
k = i;
}
} //当type为0时，求的是字符串的后缀是否为回文串
//当type为1时，求的是字符串的逆串是否为回文串。实际就是求字符串的前缀是否为回文串。
for(int i = ; i<n; i++) //判断后缀是否为回文串
ispal[type][_L+i] = (i+exd[i]==n);
} void insert(char x[], int n, int L)
{
int tmp = root;
for(int i = ; i<n; i++)
{
int ch = x[i]-'a';
node[tmp].palnum += ispal[][L+i]; //如果后缀是回文串，就把统计数放在父节点。
if(node[tmp].nxt[ch]==-) node[tmp].nxt[ch] = newnode();
tmp = node[tmp].nxt[ch];
}
node[tmp].strnum++; //字符串数+1
} int search(char x[], int n, int L)
{
int ret = ;
int tmp = root;
for(int i = ; i<n; i++)
{
int ch = x[i]-'a';
tmp = node[tmp].nxt[ch];
if(tmp==-) break;
if((i<n-&&ispal[][L+i+]) || i==n-) //x作为长串，如果剩下的部分（后缀）是回文串
ret += node[tmp].strnum;
}
if(tmp!=-) ret += node[tmp].palnum; //x作为短串，加上后缀是回文串的长串
return ret;
} int main()
{
int n;
while(scanf("%d", &n)!=EOF)
{
tot = ;
root = newnode(); int L = ;
memset(ispal, , sizeof(ispal));
for(int i = ; i<n; i++)
{
//因为不确定每个字符串的最长长度，所以只好用地址的形式存储字符串
//用string的话，速度会变慢
scanf("%d%s", &len[i], str+L);
beg[i] = L;
L += len[i];
memcpy(res+beg[i], str+beg[i], len[i]);
reverse(res+beg[i], res+beg[i]+len[i]); EXKMP(res+beg[i], len[i], str+beg[i], len[i], beg[i], ); //求字符串后缀是否为回文串
EXKMP(str+beg[i], len[i], res+beg[i], len[i], beg[i], ); //求字符串的逆串的后缀（即字符串的前缀）是否为回文串。
insert(str+beg[i], len[i], beg[i]); //插入Trie树中
} LL ans = ;
for(int i = ; i<n; i++)
ans += search(res+beg[i], len[i], beg[i]); //用字符串的逆串去查找 printf("%lld\n", ans);
}
}