Problem Description
Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.
Given a string s, we define a substring that happens exactly k times as an important string, and you need to find out how many substrings which are important strings.
Given a string s, we define a substring that happens exactly k times as an important string, and you need to find out how many substrings which are important strings.
Input
The first line contains an integer T (T≤100) implying the number of test cases.
For each test case, there are two lines:
the first line contains an integer k (k≥1) which is described above;
the second line contain a string s (length(s)≤105).
It's guaranteed that ∑length(s)≤2∗106.
For each test case, there are two lines:
the first line contains an integer k (k≥1) which is described above;
the second line contain a string s (length(s)≤105).
It's guaranteed that ∑length(s)≤2∗106.
Output
For each test case, print the number of the important substrings in a line.
Sample Input
2
2
abcabc
3
abcabcabcabc
Sample Output
6
9
题意：有一个字符串s，求其中恰好出现k次的子串有多少个？
思路：后缀数组，通过后缀数组算法可以知道每个后缀的排名，如果有某个子串恰好出现k次，那么必定有k个对应的后缀 即这个子串是这k个后缀串的前缀，那么这k个后缀串的排名一定是连续的，所以我们按排名从1~len(s)依次开始 取连续k个后缀串，可以根据height[]数组快速算出当前这k个后缀串的最大公共前缀长度len，那么长为1到len的前缀子串，这k个串都含有，设当前开始k个串为 i到i+k-1 ，那么如果子串长过短，可能 i-1 或 i+k 这个串也含有相应的子串，所以计算出 i 和 i-1 串，i+k和i+k-1的最大公共前缀长为m，那么之前取的子串长必须大于m才能保证 i-1 和 i+k 不含有相应的子串，只有i~i+k-1这k个串含有相应的子串。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1e5+;
char s[N];
int k;
int wa[N],wb[N],wv[N],wss[N];
int sa[N],ran[N],height[N];
int f[N][]; int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=; i<m; i++) wss[i]=;
for(i=; i<n; i++) wss[x[i]=(int)r[i]]++;
for(i=; i<m; i++) wss[i]+=wss[i-];
for(i=n-; i>=; i--) sa[--wss[x[i]]]=i;
for(j=,p=; p<n; j*=,m=p)
{
for(p=,i=n-j; i<n; i++) y[p++]=i;
for(i=; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=; i<n; i++) wv[i]=x[y[i]];
for(i=; i<m; i++) wss[i]=;
for(i=; i<n; i++) wss[wv[i]]++;
for(i=; i<m; i++) wss[i]+=wss[i-];
for(i=n-; i>=; i--) sa[--wss[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=,x[sa[]]=,i=; i<n; i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
return;
}
void callheight(char *r,int *sa,int n)
{
int i,j,k=;
for(i=;i<=n;i++)
ran[sa[i]]=i;
for(i=;i<n;height[ran[i++]]=k)
for(k?k--:,j=sa[ran[i]-];r[i+k]==r[j+k];k++);
return ;
}
void init(int len)
{
for(int i=;i<=len;i++) f[i][]=height[i];
for(int s=;(<<s)<=len;s++)
{
int tmp=(<<s);
for(int i=;i+tmp-<=len;i++)
{
f[i][s]=min(f[i][s-],f[i+tmp/][s-]);
}
}
}
int cal(int l,int r)
{
int len=log2(r-l+);
int ans=min(f[l][len],f[r-(<<len)+][len]);
return ans;
}
int main()
{
int T; cin>>T;
while(T--)
{
scanf("%d%s",&k,s);
int len=strlen(s);
da(s,sa,len+,);
callheight(s,sa,len);
init(len);
int ans=;
for(int i=;i+k-<=len;i++)
{
int j=i+k-;
int tmp=height[i];
if(j+<=len) tmp=max(tmp,height[j+]);
int x;
if(k!=) { x=cal(i+,j); }
else x=len-sa[i];
ans+=max(,x-tmp);
}
printf("%d\n",ans);
}
return ;
}