bzoj 1524 [POI2006]Pal

Description

给出n个回文串s1, s2, …, sn 求如下二元组(i, j)的个数 si + sj 仍然是回文串 规模 输入串总长不超过2M bytes

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

6

2 aa

3 aba

3 aaa

6 abaaba

5 aaaaa

4 abba

Sample Output

14

题解

两个串能接起来回文，那么肯定较短的那个串是较长串的一个循环节，也就是它的一个前缀。

那么对于每个串的所有前缀的串试着拼下就可以了。

具体的话搞个Trie树，然后hash一下就吼了啊

#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);
}