1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 class Suffix_Array {  ///后缀数组 5     static const int MV=20010;///串长度 6     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标，rank后缀的排名，height排名相邻两个后缀的最长公共前缀 7     bool cmp(int r[],int a,int b,int len) { 8         return r[a]==r[b]&&r[a+len]==r[b+len]; 9     }10     void buildsa() {11         int *x=wa,*y=wb;12         for(i=0; i<m; i++) ws[i]=0;13         for(i=0; i<n; i++) ws[x[i]=str[i]]++;14         for(i=1; i<m; i++) ws[i]+=ws[i-1];15         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;16         for(j=p=1; p<n; j<<=1,m=p) {17             for(p=0,i=n-j; i<n; i++) y[p++]=i;18             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;19             for(i=0; i<m; i++) ws[i]=0;20             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;21             for(i=1; i<m; i++) ws[i]+=ws[i-1];22             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];23             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;24         }25     }26     void buildheight() {27         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;28         for(i=k=0; i<n-1; height[Rank[i++]]=k)29             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);30     }31 public:32     int getsa(int id) {33         return sa[id];34     }35     int getheight(int id) {36         return height[id];37     }38     int getrank(int id) {39         return Rank[id];40     }41     void build(int s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一42         n=len;43         m=cl;44         for(int i=0; i<=len; i++) str[i]=s[i];45         str[len]=0;46         buildsa();47         buildheight();48     }49 } gx;50 int n;51 bool judge(int len) {52     int up,down;53     up=down=gx.getsa(1);54     for(int i=2; i<=n; i++) {55         if(gx.getheight(i)<len) {56             up=down=gx.getsa(i);57         } else {58             up=max(up,gx.getsa(i));59             down=min(down,gx.getsa(i));60             if(up-down>len) return true;61         }62     }63     return false;64 }65 int Bins(int L,int R) {66     while(L<=R) {67         int mid=(L+R)>>1;68         if(judge(mid)) {69             L=mid+1;70         } else {71             R=mid-1;72         }73     }74     return R+1;75 }76 int a[20010];77 int main() {78     while(~scanf("%d",&n),n) {79         for(int i=0; i<n; i++) {80             scanf("%d",&a[i]);81         }82         for(int i=0; i<n-1; i++) {83             a[i]=a[i+1]-a[i]+88;84         }85         a[n-1]=0;86         gx.build(a,n,177);87         int ans=Bins(4,n);88         if(ans<5) ans=0;89         printf("%d\n",ans);90     }91     return 0;92 }

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int M=2000100;  //可重叠的k 次最长重复子串 5 class Suffix_Array {  ///后缀数组 6     static const int MV=M;///串长度 7     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标，rank后缀的排名，height排名相邻两个后缀的最长公共前缀 8     bool cmp(int r[],int a,int b,int len) { 9         return r[a]==r[b]&&r[a+len]==r[b+len];10     }11     void buildsa() {12         int *x=wa,*y=wb;13         for(i=0; i<m; i++) ws[i]=0;14         for(i=0; i<n; i++) ws[x[i]=str[i]]++;15         for(i=1; i<m; i++) ws[i]+=ws[i-1];16         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;17         for(j=p=1; p<n; j<<=1,m=p) {18             for(p=0,i=n-j; i<n; i++) y[p++]=i;19             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;20             for(i=0; i<m; i++) ws[i]=0;21             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;22             for(i=1; i<m; i++) ws[i]+=ws[i-1];23             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];24             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;25         }26     }27     void buildheight() {28         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;29         for(i=k=0; i<n-1; height[Rank[i++]]=k)30             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);31     }32 public:33     int getsa(int id) {34         return sa[id];35     }36     int getheight(int id) {37         return height[id];38     }39     int getrank(int id) {40         return Rank[id];41     }42     void build(int s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一43         n=len;44         m=cl;45         for(int i=0; i<=len; i++) str[i]=s[i];46         str[len]=0;47         buildsa();48         buildheight();49     }50 } gx;51 int n,k;52 bool judge(int len) {53     int cnt;54     for(int i=2; i<=n; i++) {55         if(gx.getheight(i)<len) {56             cnt=1;57         } else {58             cnt++;59             if(cnt>=k) return true;60         }61     }62     return false;63 }64 int Bins(int L,int R) {65     while(L<=R) {66         int mid=(L+R)>>1;67         if(judge(mid)) {68             L=mid+1;69         } else {70             R=mid-1;71         }72     }73     return L-1;74 }75 int a[M];76 int main() {77     while(~scanf("%d%d",&n,&k)) {78         for(int i=0; i<n; i++) {79             scanf("%d",&a[i]);80             a[i]++;81         }82         gx.build(a,n+1,1000010);83         int ans=Bins(1,n);84         printf("%d\n",ans);85     }86     return 0;87 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long LL; 6 class Suffix_Array {  ///后缀数组 7     static const int MV=50010;///串长度 8     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标，rank后缀的排名，height排名相邻两个后缀的最长公共前缀 9     bool cmp(int r[],int a,int b,int len) {10         return r[a]==r[b]&&r[a+len]==r[b+len];11     }12     void buildsa() {13         int *x=wa,*y=wb;14         for(i=0; i<m; i++) ws[i]=0;15         for(i=0; i<n; i++) ws[x[i]=str[i]]++;16         for(i=1; i<m; i++) ws[i]+=ws[i-1];17         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;18         for(j=p=1; p<n; j<<=1,m=p) {19             for(p=0,i=n-j; i<n; i++) y[p++]=i;20             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;21             for(i=0; i<m; i++) ws[i]=0;22             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;23             for(i=1; i<m; i++) ws[i]+=ws[i-1];24             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];25             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;26         }27     }28     void buildheight() {29         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;30         for(i=k=0; i<n-1; height[Rank[i++]]=k)31             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);32     }33 public:34     int getsa(int id) {35         return sa[id];36     }37     int getheight(int id) {38         return height[id];39     }40     int getrank(int id) {41         return Rank[id];42     }43     void build(char s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一44         n=len;45         m=cl;46         for(int i=0; i<=len; i++) str[i]=s[i];47         str[len]=0;48         buildsa();49         buildheight();50     }51 } gx;52 char a[50010];53 int main() {54     int t;55     while(~scanf("%d",&t)) {56         while(t--){57             scanf("%s",a);58             int n=strlen(a);59             gx.build(a,n+1,256);60             LL ans=0;61             for(int i=1;i<=n;i++){62                 ans+=n-gx.getsa(i)-gx.getheight(i);63             }64             printf("%lld\n",ans);65         }66     }67     return 0;68 }