自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:09:45，当前版本为作者最后更新于2019-05-04 18:53:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置技能：后缀自动机

直接对读入的字符串建SAM，并且对其$parent$树统计$sz[u]$表示子树大小。

那么一个节点表示的字符串的出现子串出现次数就是$sz_i$

那么扫描所有$sz_i==k$的节点，该节点表示的所有子串都是可行的，而且它们的长度一定是连续的一段区间$(len_{fa_i},len_i]$

那么直接进行差分就好了，整个时间复杂度$O(n)$。

#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;

const int N=200005;

int tot=1,la,ch[N][26],fa[N],len[N],ar[N],sz[N],rk[N],cnt[N];

void extend(int id)
{
	int p=la;
	int np=++tot;
	len[np]=len[p]+1;
	while(p && !ch[p][id])
	{
		ch[p][id]=np;
		p=fa[p];
	}
	if(!p)
	{
		fa[np]=1;
	}
	else
	{
		int q=ch[p][id];
		if(len[p]+1==len[q])
		{
			fa[np]=q;
		}
		else
		{
			int nq=++tot;
			fa[nq]=fa[q];
			len[nq]=len[p]+1;
			for(int i=0; i<26; i++)
				ch[nq][i]=ch[q][i];
			fa[np]=nq;
			fa[q]=nq;
			while(p && ch[p][id]==q)
			{
				ch[p][id]=nq;
				p=fa[p];
			}
		}
	}
	++sz[la=np];
}

void Sort()
{
	for(int i=1; i<=tot; i++) ar[len[i]]++;
	for(int i=1; i<=tot; i++) ar[i]+=ar[i-1];
	for(int i=1; i<=tot; i++) rk[ar[len[i]]--]=i;
}

int T,n,k,mx,ans;

char S[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s%d",S+1,&k);
		n=strlen(S+1);
		la=1;
		for(int i=1; i<=n; i++) extend(S[i]-'a');
		Sort();
		auto upd=[](int l,int r){cnt[l]++;cnt[r+1]--;};
		for(int i=tot; i!=1; i--)
		{
			int now=rk[i];
			sz[fa[now]]+=sz[now];
			if(sz[now]==k) upd(len[fa[now]]+1,len[now]);
		}
		mx=ans=-1;
		for(int i=1; i<=n; i++)
		{
			cnt[i]+=cnt[i-1];
			if(cnt[i]>=mx)
			{
				mx=cnt[i];
				ans=i;
			}
		}
		printf("%d\n",mx>0?ans:-1);
		for(int i=1; i<=tot; i++)
		{
			len[i]=fa[i]=sz[i]=ar[i]=0;
			memset(ch[i],0,sizeof(ch[i]));
		}
		tot=1;
		for(int i=0; i<=n+1; i++) cnt[i]=0;
	}
	return 0;
}