C++(g++ 7.5.0) 解法, 执行用时: 229ms, 内存消耗: 56716K, 提交时间: 2023-05-05 01:06:06

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;

const int p = 1e9+7;
const int N = 3e5+10;

char s[N]; //cin>>(s+1) 
const int ZF=10;//字符集大小，太大就开map，或考虑后缀数组 
int son[N<<1][ZF],len[N<<1],link[N<<1]={-1};
int tot, last; //tot是最大节点(inclusive)
int cnt[N<<1]; //计算i节点子串出现次数 
void add(char c) { 
	c-='0';
	int cur = ++tot; 
	// 如果要统计子串出现次数 
	cnt[cur]++;
	len[cur] = len[last] + 1;
	int v = last;
	while (v != -1  and !son[v][c]) {  
		son[v][c] = cur;
		v = link[v];
	}
	if (v == -1) link[cur] = 0;
	else {
		int q = son[v][c];
		if (len[v] + 1 == len[q]) link[cur] = q;
		else {
			int clone = ++tot;
			len[clone] = len[v] + 1;
			for(int i = 0; i < ZF; i++) 
				son[clone][i]=son[q][i];
			link[clone] = link[q];
			while (v != -1 && son[v][c] == q) {
				son[v][c] = clone;
				v = link[v];
			}
			link[q] = link[cur] = clone;
		}
	}
	last = cur;
}
int ans[N];
vector<int> e[N<<1];
void dfs(int i){
	for(int j:e[i]){
		dfs(j);
		cnt[i]+=cnt[j];
	}
	ans[len[i]]=max(ans[len[i]],cnt[i]);
}
signed main(){
	IOS;
	int n,q; cin>>n>>q;
	cin>>(s+1);
	for(int i=1;i<=n;i++) add(s[i]);
	for(int i=1;i<=tot;i++) e[link[i]].push_back(i);
	dfs(0);
	while(q--){
		cin>>n;
		cout<<ans[n]<<'\n';
	}
}

C++ 解法, 执行用时: 116ms, 内存消耗: 32204K, 提交时间: 2021-06-20 11:33:41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,tot,last,root,q;
int a[600005],cnt[600005];
char s[600005];
int ans[600005];
struct node{
	int ch[10];
	int mx,fa,sz;
}t[600005];
void extend(int c)
{
	int cur=++tot;t[cur].mx=t[last].mx+1;
	int x=last;
	for(;!t[x].ch[c];x=t[x].fa) t[x].ch[c]=cur;
	if(!x) t[cur].fa=root;
	else if(t[t[x].ch[c]].mx==t[x].mx+1) t[cur].fa=t[x].ch[c];
	else
	{
		int y=++tot,o=t[x].ch[c];
		t[y].mx=t[x].mx+1;
		memcpy(t[y].ch,t[o].ch,sizeof(t[y].ch));
		t[y].fa=t[o].fa;t[cur].fa=t[o].fa=y;
		for(;x&&t[x].ch[c]==o;x=t[x].fa) t[x].ch[c]=y;
	}
	last=cur;
	t[cur].sz=1;
}
void calc()
{
	for(int i=1;i<=tot;i++) cnt[t[i].mx]++;
	for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;i++) a[cnt[t[i].mx]--]=i;
	for(int i=tot;i>=1;i--)
	{
		int x=a[i];
		t[t[x].fa].sz+=t[x].sz;
		ans[t[x].mx]=max(ans[t[x].mx],t[x].sz);
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	root=tot=last=1;
	for(int i=1;i<=n;i++) extend(s[i]-'0');
	calc();
	for(int i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	return 0;
}