rt，赛时写了一个类似 KMP 的东西，但是会被非随机数据卡到 $O(n^2)$，只拿到了 $25$ pts，求助一下正解思路。

贴一下 $25$ pts 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
string b;
int nxt[N],n,m,ans，cnt;

vector<int> t[N];
int pre[N];
int main(){
//	freopen("T4.in","r",stdin);
//	freopen("T4.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>b;
	for(int i=1;i<=n;++i) {
		pre[i]=i-1;
	}
	for(int i=1;i<n;++i){
		int j=nxt[i-1];
		while(j&&b[j]!=b[i]) 
			j=nxt[j-1];
		if(b[j]==b[i]) j++;
		nxt[i]=j; 
		if(i-pre[j]>=j) {
			pre[j]=i;
			t[j].push_back(i);
		} 
		while(j!=0){
			j=nxt[j-1]; 
			if(i-pre[j]>=j) {
				pre[j]=i;
				t[j].push_back(i);
			} 
		}
	}
	cin>>m;
	for(int f,k,i=1;i<=m;++i){
		cin>>f>>k; ans=0;
		int temp=f;
		if(k==1){
			cout<<"1\n"; continue;
		}
		else{
			while(f!=0){
				f=nxt[f-1];
				if(t[f].size()>=k-1&&t[f][k-2]<temp) ans++;
			}
			cout<<ans-1<<'\n';
		}
	}
	return 0;
}