告訴你一個字元串和k , 求這個字元串中有多少不同的子串恰好出現了k 次。
思路:
字尾數組。
我們先考慮至少出現k 次的子串, 是以我們枚舉排好序的字尾i (sa[i]) 。
k段k 段的枚舉。
假設目前枚舉的是 sa[i]~sa[i + k -1]
那麼假設這一段的最長公共字首 是L 的話。
那麼就有L 個不同的子串至少出現了k次。
我們要減去至少出現k + 1次的 , 但還要和這個k 段的lcp 有關系, 是以肯定就是 這一段 向上找一個字尾 或者向下找一個字尾。
即 sa[i-1] ~ sa[i + k - 1] 和 sa[i] ~ sa[i + k] 求兩次lcp 減去即可。
但是會減多了。
減多的顯然是sa[i-1] ~ sa[i + k] 的lcp。 加上即可。
注意 k =1的情況在求lcp 會有 問題, 即求一個串的最長公共字首會有問題, 特判一下即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100000+100;
int sa[maxn],Rank[maxn],lcp[maxn],dis[maxn][20];
int now[maxn],x[maxn],y[maxn],c[maxn];
char ch[maxn];
int n,m;
inline void getSa(){
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[i]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int tot=0;
for(int i=n-k;i<n;i++) y[tot++]=i;
for(int i=0;i<n;i++) if(sa[i]>=k) y[tot++]=sa[i]-k;
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
int p=0;
x[sa[0]]=p++;
for(int i=1;i<n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p-1:p++;
if(p>=n) break;
m=p;
}
int k=0;
for(int i=0;i<n;i++) Rank[sa[i]]=i;
for(int i=0;i<n-1;i++){
if(k) k--;
int j=sa[Rank[i]-1];
while(now[i+k]==now[j+k]) k++;
lcp[Rank[i]]=k;
}
}
inline void Rmq(){
for(int i=0;i<n;i++) dis[i][0]=lcp[i];
for(int i=1;(1<<i)<=n;i++){
for(int j=0;j+(1<<i)-1<n;j++){
dis[j][i]=min(dis[j][i-1],dis[j+(1<<(i-1))][i-1]);
}
}
}
inline int getMin(int l,int r){
if(l==r) return n-sa[l]-1;
l++;
int i=0;
while((1<<(i+1))<(r-l+1)) i++;
return min(dis[l][i],dis[r-(1<<i)+1][i]);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int num;
scanf("%d %s",&num,ch);
n=strlen(ch);
m=27;
for(int i=0;i<n;i++) now[i]=x[i]=ch[i]-'a'+1;
now[n]=x[n]=0;
n++;
getSa();
Rmq();
ll ans=0;
for(int i=1;i<=n-num;i++){
ans+=(ll)getMin(i,i+num-1);
if(i-1>=1) ans-=(ll)getMin(i-1,i+num-1);
if(i+num<n) ans-=(ll)getMin(i,i+num);
if(i-1>=1 && i+num<n) ans+=(ll)getMin(i-1,i+num);
}
printf("%lld\n",ans);
}
}