Description
The “repetitions” of a string S(whose length is n) is a maximum number “k” such that: 1) k is a factor of n 2) S[0..n/k-1] = S[p*(n/k)..(p+1)*(n/k)-1] for all that (1 <= p < n/k) for example: the repetitions of “aaaaaa”is 6. the repetitions of “abababab”is 4. the repetitions of “abcdef”is 1. Now, given a string S and a number K, please tell me how many substrings of S have repetitions NOT less than K.
Input
The input consists of several instances, each one for a single line. S K S is a string, K is a number. Check the Description for their meanings. S contains lowercase letters(ie 'a'..'z') only. 1 <= length of S <= 100000. 1 <= K <= length of S.
Output
For each instance, output the number of substring whose repetitions is NOT less than K.
Sample Input
abcabc 2
acmac 3
Sample Output
1
0 先记录一下，完全不知道怎么回事。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=;
int height[maxn],sa[maxn],rank[maxn],c[maxn],t1[maxn],t2[maxn];
void da(int *str,int n,int m)
{
int i,j,k,p,*x=t1,*y=t2;
for(i=;i<m;i++)c[i]=;
for(i=;i<n;i++)c[x[i]=str[i]]++;
for(i=;i<m;i++)c[i]+=c[i-];
for(i=n-;i>=;i--)sa[--c[x[i]]]=i;
for(k=;k<=n;k<<=)
{
p=;
for(i=n-k;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=;i<m;i++)c[i]=;
for(i=;i<n;i++)c[x[y[i]]]++;
for(i=;i<m;i++)c[i]+=c[i-];
for(i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p-:p++;
if(p>=n)break;
m=p;
}
}
void calheight(int *str,int n)
{
int i,j,k=;
for(i=;i<=n;i++)rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k)k--;
j=sa[rank[i]-];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
// printf("sa:");for(i=0;i<=n;i++)printf("%d ",sa[i]);puts("");
// printf("rank:");for(i=0;i<=n;i++)printf("%d ",rank[i]);puts("");
// printf("height:");for(i=0;i<=n;i++)printf("%d ",height[i]);puts(""); }
int str[maxn];
char ss[maxn];
int Log[maxn];
int best[][maxn];
void init(int n)
{
int i,j;
Log[]=-;
for(i=;i<=n;i++)
Log[i]=(i&(i-))?Log[i-]:Log[i-]+;
for(i=;i<=n;i++)best[][i]=height[i];
for(i=;i<=Log[n];i++)
for(j=;j<=n;j++)
best[i][j]=min(best[i-][j],best[i-][j+(<<(i-))]);
}
int lcp(int a,int b)
{
a=rank[a];
b=rank[b];
if(a>b)swap(a,b);
a++;
int t=Log[b-a+];
return min(best[t][a],best[t][b-(<<t)+]);
}
int rep[maxn];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n,p;
while(~scanf("%s%d",&ss,&k))
{
n=strlen(ss);
if(k==)
{
printf("%lld\n",(long long)n*(n+)/);
continue;
}
for(i=;i<n;i++)str[i]=ss[i];
str[n]=;
da(str,n+,);
calheight(str,n);
init(n);
for(i=;i<=n;i++)rep[i]=;
for(int L=;L*k<=n;L++)
{
for(i=;i<n;i+=L)
{
int t=lcp(i,i+L);
if(!t)continue;
j=;
while(j<=i&&j<L&&str[i-j]==str[i-j+L])
{
if(t>=L&&lcp(i-j,i-j+L)>=(k-)*L)
rep[i-j]=max(rep[i-j],t/L+);
j++;t++;
}
}
}
int ans=;
for(i=;i<=n;i++)if(rep[i]>=k)ans+=rep[i]-k+;
printf("%d\n",ans);
}
return ;
}