求字符串内的非空子串的数量
后缀数组！！！
1 #include<algorithm> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 8 typedef long long LL; 9 10 #define N 1510 11 12 int wa[N],wb[N],ws[N],wv[N]; 13 int rank[N],height[N],sa[N]; 14 int r[N]; 15 16 char s[N]; 17 18 int ans; 19 20 int cmp(int *r,int a,int b,int l) 21 { 22 return r[a]==r[b] && r[a+l]==r[b+l]; 23 } 24 25 void da(int *r,int n,int m) 26 { 27 int i,j,p,*x=wa,*y=wb,*t; 28 for (i=0;i<m;i++) ws[i]=0; 29 for (i=0;i<n;i++) ws[x[i]=r[i]]++; 30 for (i=1;i<m;i++) ws[i]+=ws[i-1]; 31 for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; 32 for (j=1,p=1;p<n;j<<=1,m=p) 33 { 34 for (p=0,i=n-j;i<n;i++) y[p++]=i; 35 for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j; 36 for (i=0;i<n;i++) wv[i]=x[y[i]]; 37 for (i=0;i<m;i++) ws[i]=0; 38 for (i=0;i<n;i++) ws[wv[i]]++; 39 for (i=1;i<m;i++) ws[i]+=ws[i-1]; 40 for (i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i]; 41 for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) 42 x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p-1 : p++; 43 } 44 return ; 45 } 46 47 void calheight(int *r,int n) 48 { 49 int i,j,k=0; 50 for (i=1;i<=n;i++) rank[sa[i]]=i; 51 for (i=0;i<n;height[rank[i++]]=k) 52 for (k ? k-- : 0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); 53 return ; 54 } 55 56 int main() 57 { 58 scanf("%s",s); 59 int n=strlen(s); 60 for (int i=0;i<n;i++) 61 r[i]=s[i]-'A'+2; 62 r[n]=0; 63 da(r,n+1,300); 64 calheight(r,n); 65 for(int i=0;i<n;i++) 66 ans+=n-i-height[rank[i]]; 67 printf("%d",ans); 68 return 0; 69 }
还可以用Trie，短多了。。。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include<iostream> 5 #include<bitset> 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 char s[1505]; 9 int sum,i,j,len,u,ch[1200000][26]; 10 int main() 11 { 12 scanf("%s",s); 13 len=strlen(s); 14 for(i=0;i<len;i++) 15 { 16 u=0; 17 for(j=i;j<len;j++) 18 { 19 int c=s[j]-'A'; 20 if(!ch[u][c]) ch[u][c]=++sum; 21 u=ch[u][c]; 22 } 23 } 24 cout<<sum<<endl; 25 return 0; 26 }