# bzoj 1524 [POI2006]Pal

### 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

6

2 aa

3 aba

3 aaa

6 abaaba

5 aaaaa

4 abba

14

### 题解

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#define ull unsigned long long
#define N 2000010
using namespace std;
ull ha[N],times[N],base=131,ans;
int len[N],ch[N][27],sums[N],is_end[N],n,root=1,sz=1;
string s[N];
char s1[N];
main()
{
times[0]=1;
for (int i=1;i<=N-10;i++)
times[i]=times[i-1]*base;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&len[i]);
scanf("%s",s1);
s[i]=s1;
//      cin>>s[i];
int now=root;
for (int j=0;j<len[i];ha[i]=(ha[i]*base+s[i][j]-'a'+1),j++)
if (ch[now][s[i][j]-'a'+1])
now=ch[now][s[i][j]-'a'+1];
else
now=ch[now][s[i][j]-'a'+1]=++sz;
is_end[now]=i;
sums[now]++;
}
for (int i=1;i<=n;i++)
{
int now=root;
for (int j=0;j<len[i];j++)
{
now=ch[now][s[i][j]-'a'+1];
if (is_end[now] && ha[is_end[now]]*times[len[i]]+ha[i]==ha[i]*times[j+1]+ha[is_end[now]])
ans+=(ull)sums[now]*2;
}
}
printf("%lld\n",(long long)ans-n);
}