首页 > 代码库 > poj 3376 Finding Palindromes
poj 3376 Finding Palindromes
| Time Limit: 10000MS | Memory Limit: 262144K | |
| Case Time Limit: 2000MS | ||
Description
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
31 a2 ab2 ba
Sample Output
5
Hint
aa aba aba abba baab
#include<cstdio>#include<cstring>#include<algorithm>#define N 2000008using namespace std;bool f[2][N];long long ans;char T[N],S[N];int len,tot,root,id;int st[N],ed[N],cnt;int nxt[N],expand[N];int trie[N][26],mark[N],sum[N];void getnxt(char *s,int ll,int rr){ int a=ll; nxt[0]=rr-ll+1; while(a+1<=rr && s[a]==s[a+1]) a++; nxt[1]=a-ll; a=1+ll; int p,l,j; for(int k=2+ll;k<=rr;k++) { p=a-ll+nxt[a-ll]-1; l=nxt[k-a]; if(k-ll+l-1>=p) { j=p-k+ll+1>0 ? p-k+ll+1 : 0; while(k+j<=rr && s[k+j]==s[j+ll]) j++; nxt[k-ll]=j; a=k; } else nxt[k-ll]=l; }}void exkmp(char *s,char *t,int ll,int rr,int w){ getnxt(t,ll,rr); int a=ll; while(a<=rr && s[a]==t[a]) a++; expand[0]=a-ll; a=ll; int p,l,j; for(int k=ll+1;k<=rr;k++) { p=a-ll+expand[a-ll]-1; l=nxt[k-a]; if(k-ll+l-1>=p) { j=p-k+ll+1>0 ? p-k+ll+1 : 0; while(k+j<=rr && s[k+j]==t[j+ll]) j++; expand[k-ll]=j; a=k; } else expand[k-ll]=l; } for(int i=ll-ll;i<=rr-ll;i++) if(i+expand[i]==rr-ll+1) f[w][i+ll]=true;}void insert(int ll,int rr){ root=0; for(int i=ll;i<=rr;i++) { id=S[i]-‘a‘; sum[root]+=f[0][i]; if(!trie[root][id]) trie[root][id]=++tot; root=trie[root][id]; } mark[root]++;}void find(int ll,int rr){ root=0; for(int i=ll;i<=rr;i++) { id=T[i]-‘a‘; root=trie[root][id]; if(!root) return; if(i!=rr&&f[1][i+1] || i==rr) ans+=mark[root]; } ans+=sum[root];}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%s",&len,S+cnt); for(int j=0;j<len;j++) T[cnt+j]=S[cnt+len-j-1]; st[i]=cnt; ed[i]=cnt+len-1; exkmp(S,T,st[i],ed[i],0); exkmp(T,S,st[i],ed[i],1); cnt+=len; insert(st[i],ed[i]); } for(int i=1;i<=n;i++) find(st[i],ed[i]); printf("%lld\n",ans);}
poj 3376 Finding Palindromes