Finding Palindromes （exkmp+trie）

https://cn.vjudge.net/problem/POJ-3376

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

The 5 palindromes are: 

a a a ba ab a ab ba ba ab 

題意：

給定n個字元串。問把他們兩兩組合起來(包括自己和自己組合），能有多少個回文串。

字元串s與字元串t組合要想組成回文串

1.lens = lent,   s = rt  (rt為t的反串）

2.lens > lent,  rt 是 s 的字首，且s剩下的部分是回文串

3.lens < lent,  s 是 rt 的字首，且rt剩下的部分是回文串

可以先用一個擴充kmp，利用其extend數組求出每個串的最長回文字尾和最長回文字首

把原串建一棵字典樹，用反串比對

book[0][i]表示原串剩下的部分是回文串

book[1][i]表示反串剩下的部分是回文串

num[i]表示以該節點為結尾的原串的數量

val[i]表示從i往後是回文串的數量

出題人太狠，時間和空間卡的太狼滅了

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
const int maxc=26;
char s[maxn],rs[maxn];
int l[maxn],r[maxn];
bool book[2][maxn];
int Next[maxn];//T[i]...T[m - 1]與T的最長相同字首長度；
int extend[maxn];//S[i]...S[n - 1]與T的最長相同字首長度。
/*求解T中Next[]，注釋參考GetExtend()*/
void GetNext(char T[],int &m,int Next[]){
	int a=0,p=0;
	Next[0]=m;
	for(int i=1;i<m;i++){
		if(i>=p||i+Next[i-a]>=p){
			if(i>=p)
				p=i;
 
			while(p<m&&T[p]==T[p-i])
				p++;
 
			Next[i]=p-i;
			a=i;
		}else
			Next[i]=Next[i-a];
	}
}
 
/*求解extend[]*/
void GetExtend(char S[],char T[],int extend[],int Next[],int flag,int l){
	int a=0,p=0;
	int n=strlen(S);
    int m=strlen(T);
	GetNext(T,m,Next);
	for(int i=0;i<n;i++){
		if(i>=p||i+Next[i-a]>=p){//i>=p的作用：舉個典型例子，S和T無一字元相同
			if(i>=p)
				p=i;
 
			while(p<n&&p-i<m&&S[p]==T[p-i])
				p++;
 
			extend[i]=p-i;
			a=i;
		}else
			extend[i]=Next[i-a];
	}
	for(int i=0;i<n;i++){
		if(i+extend[i]==n) book[flag][l+i]=true;
	}
}
int root=1;
int tot=0;
struct TRIE{
	int Next[maxn][maxc];
	int num[maxn];
	int val[maxn];
	int base;
	void init(){
		for(int i=0;i<=tot;i++) {
			memset(Next[i],0,sizeof(Next[i]));
			num[i]=0;
			val[i]=0;
		}
		tot=1;
	}
	void add(char s[],int now,int l){
		int len=strlen(s);
		for(int i=0;i<len;i++){
			int c=s[i]-base;
			val[now]+=book[0][l+i];
			if(!Next[now][c]){
			 Next[now][c]=++tot;
			} 
			now=Next[now][c];
		}
		num[now]++;
	}
	ll find(char s[],int len,int now,int l){
		ll ans=0;
		for(int i=0;i<len;i++){
			int c=s[i]-base;
			now=Next[now][c];
			if(!now) break;
			if((i<len-1&&book[1][l+i+1])||(i==len-1)) ans+=num[now];
		} 
		if(now) ans+=val[now];
		return ans; 
	}
}tr;
int main(){
    int n; 
    scanf("%d",&n);
    tr.init();
    tr.base='a';
    int sumlen=0;
	for(int i=1;i<=n;i++){
		int len;
		scanf("%d%s",&len,s+sumlen);
		int Len=sumlen+len;
		for(int j=0;j<len;j++){
			rs[sumlen+j]=s[sumlen+len-j-1];
		}
		l[i]=sumlen;
		r[i]=Len-1;
		sumlen=Len;
	    GetExtend(s+l[i],rs+l[i],extend,Next,0,l[i]);
	    GetExtend(rs+l[i],s+l[i],extend,Next,1,l[i]);
	    tr.add(s+l[i],1,l[i]);	
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		ans+=tr.find(rs+l[i],r[i]-l[i]+1,1,l[i]);
	}
	printf("%lld\n",ans);
	return 0;
}