枚举子串长度，根据height分组，如果本组sa最小值与sa最大值之差超过枚举的长度，则本组对于答案贡献为1。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <string> 5 #include <string.h> 6 #include <stdio.h> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <ctime> 13 #include <cassert> 14 #include <sstream> 15 using namespace std; 16 17 const int N=223456; 18 const int MOD=1e9+7; 19 20 21 char s[N]; 22 struct SuffixArray {; 23 int sa[N]; 24 int t1[N],t2[N],c[N]; 25 int rk[N],height[N]; 26 27 inline int cmp(int *r,int a,int b,int l){ 28 return r[a]==r[b]&&r[a+l]==r[b+l]; 29 } 30 void calcSA (char *s,int n,int m) { 31 int i,j,p,*x=t1,*y=t2; 32 for(i=0;i<m;i++)c[i]=0; 33 for(i=0;i<n;i++)c[x[i]=s[i]]++; 34 for(i=1;i<m;i++)c[i]+=c[i-1]; 35 for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i; 36 for(j=1;j<=n;j<<=1){ 37 p=0; 38 for(i=n-j;i<n;i++)y[p++]=i; 39 for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j; // 排名从小到大，如果pos比j大，则suffix(sa[i]-j)的第二关键字为p 40 for(i=0;i<m;i++)c[i]=0; 41 for(i=0;i<n;i++)c[x[y[i]]]++; 42 for(i=1;i<m;i++)c[i]+=c[i-1]; 43 for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i]; // 根据第二关键字从大到小，确定新一轮sa 44 swap(x,y); 45 p=1;x[sa[0]]=0; 46 for(i=1;i<n;i++) 47 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 48 if(p>=n)break; 49 m=p; 50 } 51 } 52 void calcHeight(char *s,int n) { 53 int i,j,k=0; 54 for(i=0;i<=n;i++)rk[sa[i]]=i; 55 for(i=0;i<n;i++){ 56 if(k)k--; // h[i]>=h[i-1]-1 57 j=sa[rk[i]-1]; // suffix(j)排名在suffix(i)前一位 58 while(s[i+k]==s[j+k])k++; // 暴力计算lcp 59 height[rk[i]]=k; 60 } 61 } 62 int lcp(int a,int b,int len) { 63 if (a==b) return len-a; 64 int ra=rk[a],rb=rk[b]; 65 if (ra>rb) swap(ra,rb); 66 return queryST(ra+1,rb); 67 } 68 69 int st[N][25];//第二维要保证大于log(N<<1) 70 void initST(int n) { 71 for (int i=1; i<=n; i++) 72 st[i][0]=height[i]; 73 for (int j=1; (1<<j)<=n; j++) { 74 int k=1<<(j-1); 75 for (int i=1; i+k<=n; i++) 76 st[i][j]=min(st[i][j-1],st[i+k][j-1]); 77 } 78 } 79 int queryST(int a,int b) { 80 if (a>b) swap(a,b); 81 int dis=b-a+1; 82 int k=log((double)dis)/log(2.0); 83 return min(st[a][k],st[b-(1<<k)+1][k]); 84 } 85 }suf; 86 87 int main () { 88 while (scanf("%s",s)!=EOF){ 89 if (s[0]=='#') break; 90 int n=strlen(s); 91 suf.calcSA(s,n+1,128); 92 suf.calcHeight(s,n); 93 //for (int i=0;i<=n;i++) cout<<suf.sa[i]<<" ";cout<<endl; 94 //for (int i=0;i<=n;i++) cout<<suf.height[i]<<" ";cout<<endl; 95 int ret=0; 96 for (int i=1;i<=n/2;i++) { 97 int mi=suf.sa[1],ma=suf.sa[1]; 98 for (int j=2;j<=n;j++) { 99 if (suf.height[j]<i) { 100 if (mi+i<=ma) ret++; 101 mi=suf.sa[j]; 102 ma=suf.sa[j]; 103 104 } 105 mi=min(mi,suf.sa[j]); 106 ma=max(ma,suf.sa[j]); 107 } 108 if (mi+i<=ma) ret++; 109 } 110 cout<<ret<<endl; 111 } 112 return 0; 113 }