很不错的一个题（注意string会超时）
题意：给你n串字符串，问你两两匹配形成n*n串字符串中有多少个回文串
题解：我们首先需要想到多串字符串存储需要trie树（关键），然后我们正序插入倒序匹配就可以O（len）找到回文串个数了。
但是如果每次直接查询到结尾的话会漏掉两种情况
如： 1：a 与 ba 匹配（使用的是ab去匹配a）
2：ab 与 a 匹配
对于2这种情况我们需要在trie树记录每个字符串每个后缀可以形成回文串的个数（建树时就维护），对于1我们则需在匹配时看查询串每个后缀是否形成回文串。
扩展KMP：对于字符串str1的每一位与str2的最长前缀匹配记为ntand。
首先求得str1对于自己的每一位的“ntand”记为nnext，接着根据nnext求得ntand（两个函数想法与写法几乎一致）。
求nnext：我们首先暴力匹配第1个，接着根据字符串那面求得的匹配信息无回溯的求下一位
至于寻找每个后缀是否形成回文串我们使用扩展KMP的字符串正序和倒序的匹配长度来计算。
具体看代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
struct node
{
int next[];
int coun,npd;//此处结束的单词个数 接下来是回文的单词个数
void init()
{
memset(next,,sizeof(next));
coun=npd=;
}
} trie[Max];
int nnext[Max],ntand[Max];
void Exnext(int len,char *str)//扩展KMP求next数组：是数组此对应位置与开头的最长公共前缀
{
nnext[]=len;
nnext[]=;
for(int i=; i+<len&&str[i]==str[i+]; ++i) //暴力匹配第二位
nnext[]++;
int k=;//最远匹配的下标
int p,l,j;
for(int i=; i<len; ++i)
{
p=k+nnext[k]-;
l=nnext[i-k];
if(i+l<=p)//可以画图来看，一定是匹配的
nnext[i]=l;
else
{
j=p-i+;//不确定的位置
if(j<)
j=;
while(i+j<len&&str[j]==str[i+j])//可以无回溯的暴力匹配
++j;
nnext[i]=j;
k=i;
}
}
return;
}
void Extand(int len,char *str1,char *str2)//两字符串的最长公共前缀
{
Exnext(len,str1);//正序的每一位和倒序相匹配 求辅助数组
ntand[]=;//之后与辅助数组一样
for(int i=; i<len&&str1[i]==str2[i]; ++i)
ntand[]++;
int k=;
int l,p,j;
for(int i=; i<len; ++i)
{
p=k+ntand[k]-;
l=nnext[i-k];
if(i+l<=p)
ntand[i]=l;
else
{
j=p-i+;
if(j<)
j=;
while(i+j<len&&str1[j]==str2[i+j])
++j;
ntand[i]=j;
k=i;
}
}
return ;
}
char str1[Max],str2[Max];
int len[Max],tot;
void Insert(int j,char *str)//trie树插入
{
int now=,mpos;
for(int i=; i<len[j]; ++i)
{
mpos=str[i]-'a';
if(!trie[now].next[mpos])
{
trie[now].next[mpos]=++tot;
trie[tot].init();
}
now=trie[now].next[mpos];
if(i<len[j]-&&ntand[i+]==len[j]-i-)//此位置之后是回文串
{
trie[now].npd++;
} }
trie[now].coun++;
return;
}
char str[Max];
ll Search(int j)
{
ll ans=0ll;
int now=,mpos;
for(int i=; i<len[j]; ++i)
{
mpos=str2[i]-'a';//倒序
if(!trie[now].next[mpos])
return ans;
now=trie[now].next[mpos];
if(i<len[j]-&&ntand[i+]==len[j]-i-)//此位置之后是回文串
ans+=(ll)trie[now].coun;
}
return ans+(ll)trie[now].coun+(ll)trie[now].npd;//匹配结束
}
int main()
{
int n;
while(~scanf("%d",&n))
{
tot=;
trie[tot].init();
int sum=;
for(int i=; i<n; ++i)
{
scanf("%d %s",&len[i],str+sum);
int coun=;
for(int j=len[i]-;j>=;--j) //倒序
str2[coun++]=str[j+sum];
for(int j=; j<len[i]; ++j)
str1[j]=str[j+sum];
str1[len[i]]=str2[len[i]]='\0';
Extand(len[i],str2,str1);
Insert(i,str1);//正序来插入
sum+=len[i];
}
ll ans=0ll;
sum=;
for(int i=; i<n; ++i)
{
for(int j=; j<len[i]; ++j)
{
str1[j]=str[j+sum];
str2[j]=str[len[i]-j-+sum];
}
str1[len[i]]=str2[len[i]]='\0';
Extand(len[i],str1,str2);
ans+=Search(i);//倒序查询
sum+=len[i];
}
printf("%lld\n",ans);
}
return ;
}