Trie+哈希随便搞搞就行了。
#SXOI2016之蜜汁错误# 考场上忘记每个串都是回文串，想复杂了，最后只拿了30，剩下70全部TLE。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define ull unsigned long long
#define maxn 2000005
#define base 233
using namespace std;
int n,tot=1;
int l[maxn],cnt[maxn],num[maxn],t[maxn][26];
ll ans;
ull ha[maxn],p[maxn];
char ch[maxn];
string s[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
p[0]=1;F(i,1,2000000) p[i]=p[i-1]*base;
n=read();
F(i,1,n)
{
l[i]=read();
scanf("%s",ch);s[i]=ch; //字符串这样读入更快
// cin>>s[i]; //TLE
int now=1;ull tmp=0;
F(j,0,l[i]-1)
{
int x=s[i][j]-'a';
if (!t[now][x]) t[now][x]=++tot;
now=t[now][x];
tmp=tmp*base+(ull)(x+1);
}
cnt[now]++;num[now]=i;ha[i]=tmp;
}
F(i,1,n)
{
int now=1;
F(j,0,l[i]-1)
{
now=t[now][s[i][j]-'a'];
if (cnt[now]&&ha[num[now]]*p[l[i]]+ha[i]==ha[i]*p[l[num[now]]]+ha[num[now]]) ans+=cnt[now];
}
}
ans=ans*2-n;
printf("%lld\n",ans);
return 0;
}
原文：http://blog.csdn.net/aarongzk/article/details/51195450