后缀数组求有多少个不同的回文串
The Number of PalindromesTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1976Accepted Submission(s): 690
Problem Description
Now, you are given a string S. We want to know how many distinct substring of S which is palindrome.
Input
The first line of the input contains a single integer T(T<=20), which indicates number of test cases.Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.
Output
For every test case, you should output "Case #k:" first in a single line, where k indicates the case number and starts at 1. Then output the number of distinct substring of S which is palindrome.
Sample Input
3aaaaabababcd
Sample Output
Case #1: 4Case #2: 4Case #3: 4
Source
2011 Multi-University Training Contest 11 – Host by UESTC
/* ***********************************************Author:CKbossCreated Time :2015年04月05日 星期日 14时46分57秒File Name:HDOJ3948.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int maxn = 220000;int sa[maxn],rank[maxn],rank2[maxn],h[maxn];int c[maxn],*x,*y,ans[maxn];char str[maxn];void init(){memset(sa,0,sizeof(sa));memset(str,0,sizeof(str));memset(rank,0,sizeof(rank));}bool cmp(int* r,int a,int b,int l,int n){if(r[a]==r[b]&&a+l<n&&b+l<n&&r[a+l]==r[b+l]) return true;return false;}void radix_sort(int n,int sz){for(int i=0;i<sz;i++) c[i]=0;for(int i=0;i<n;i++) c[x[y[i]]]++;for(int i=1;i<sz;i++) c[i]+=c[i-1];for(int i=n-1;i>=0;i–) sa[–c[x[y[i]]]]=y[i];}void get_sa(char c[],int n,int sz=128){x=rank,y=rank2;for(int i=0;i<n;i++) x[i]=c[i],y[i]=i;radix_sort(n,sz);for(int len=1;len<n;len=len*2){int yid=0;for(int i=n-len;i<n;i++) y[yid++]=i;for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len;radix_sort(n,sz);swap(x,y);x[sa[0]]=yid=0;for(int i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid;sz=yid+1;if(sz>=n) break;}for(int i=0;i<n;i++) rank[i]=x[i];}void get_h(char str[],int n) {int k=0; h[0]=0;for(int i=0;i<n;i++){if(rank[i]==0) continue;k=max(k-1,0);int j=sa[rank[i]-1];while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++;h[rank[i]]=k;}} int dp[maxn][20],Log[maxn];void RMQ_init(int n){memset(dp,63,sizeof(dp));for(int i=0;i<n;i++) dp[i][0]=h[i];for(int i=1;i<=Log[n];i++)for(int j=0;j+(1<<i)-1<n;j++)dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);}int lcp(int l,int r){l=rank[l],r=rank[r];if(l>r) swap(l,r);int a=l+1,b=r;int k=Log[b-a+1];return min(dp[a][k],dp[b-(1<<k)+1][k]);}void PRE(){int m=strlen(str);for(int i=0;i<m;i++) str[i+m+1]=str[m-1-i];str[m]='$';str[2*m+1]=0;}int main() {Log[0] = -1;for(int i=1;i<=maxn;i++) Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ;int T_T,cas=1;scanf("%d",&T_T);while(T_T–){init();scanf("%s",str);PRE();int n=strlen(str);get_sa(str,n);get_h(str,n);RMQ_init(n);/********* gao ************/int pre1=0,pre2=0,l,ans=0;for(int i=1;i<n;i++){pre1=min(pre1,h[i]);l=lcp(sa[i],n-1-sa[i]);if(l>pre1){ans+=l-pre1;pre1=l;}pre2=min(pre2,h[i]);l=lcp(sa[i],n-sa[i]);if(l>pre2){ans+=l-pre2;pre2=l;}}printf("Case #%d: %d\n",cas++,ans);}return 0;}
，勇气执着的背负起那厚重的行囊，奔向远方。
