【题解】Luogu P5341 [TJOI2019]甲苯先生和大中锋的字符串

原题传送门

实际按照题意模拟就行

我们先求出字符串的sa

因为要在字符串中出现k次，所以我们枚举\(l,r(r-l+1=k)\)看一共有多少种合法的方案

合法方案的长度下界\(lb\)为\(Max(height[l],lcp(l,r+1))+1\)，这样保证子串在[1,l-1]和[r+1,len]中不会作为前缀

合法方案的长度上界\(rb\)为\(lcp(l,r)\)，毕竟要求的是出现了k次的字串

如果\(lb<=rb\)我们就进行差分，否则就是没有可行方案

最后差分求前缀和时顺带比最大值即可

数据千万条，清空第一条。

多测不清空，爆零两行泪。

#include <bits/stdc++.h>

#define N 100005

using namespace std;

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Min(register int a,register int b)

{

	return a<b?a:b;

}

inline int Max(register int a,register int b)

{

	return a>b?a:b;

}

char s[N];

int n,size,tp[N],rak[N],sa[N],tex[N],height[N];

int lg2[N],st[N][25];

inline void Qsort()

{

	for(register int i=0;i<=size;++i)

		tex[i]=0;

	for(register int i=1;i<=n;++i)

		++tex[rak[i]];

	for(register int i=1;i<=size;++i)

		tex[i]+=tex[i-1];

	for(register int i=n;i>=1;--i)

		sa[tex[rak[tp[i]]]--]=tp[i];

}

inline void sa_build()

{

	for(register int i=1;i<=(n<<1)&&i<N;++i)

		tp[i]=rak[i]=0;

	size=30;

	for(register int i=1;i<=n;++i)

		rak[i]=s[i]-'a'+1,tp[i]=i;

	Qsort();

	for(register int w=1,p=0;p<n;size=p,w<<=1)

	{

		p=0;

		for(register int i=1;i<=w;++i)

			tp[++p]=n-w+i;

		for(register int i=1;i<=n;++i)

			if(sa[i]>w)

				tp[++p]=sa[i]-w;

		Qsort();

		swap(tp,rak);

		rak[sa[1]]=p=1;

		for(register int i=2;i<=n;++i)

			rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;

	}

}

inline void getheight()

{

	int k=0;

	for(register int i=1;i<=n;++i)

	{

		if(k)

			--k;

		int j=sa[rak[i]-1];

		while(s[i+k]==s[j+k])

			++k;

		height[rak[i]]=k;

	}

}

inline void st_build()

{

	memset(st,0,sizeof(st));

	for(register int i=1;i<=n;++i)

		st[i][0]=height[i];

	for(register int j=1;(1<<j)<=n;++j)

		for(register int i=1;i+(1<<j)-1<=n;++i)

			st[i][j]=Min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

}

inline int getlcp(register int l,register int r)

{

    ++l;

    int k=lg2[r-l+1];

    return Min(st[l][k],st[r-(1<<k)+1][k]);

}

int T,m,cnt[N];

int main()

{

	lg2[0]=-1;

	for(register int i=1;i<N;++i)

		lg2[i]=lg2[i>>1]+1;

	lg2[0]=0;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s%d",s+1,&m);

		n=strlen(s+1);

		sa_build();

		getheight();

		st_build();

		memset(cnt,0,sizeof(cnt));

		for(register int i=1,x;i<=n;++i)

			if(m==1)

			{

				if((x=Max(height[i],height[i-1]))<n-sa[i]+1);

					++cnt[x+1],--cnt[n-sa[i]+2];

			}

			else

			{

				int l=Max(height[i],getlcp(i,i+m))+1;

				int r=getlcp(i,i+m-1);

				if(l<=r)

					++cnt[l],--cnt[r+1];

			}

		for(register int i=1;i<=n;++i)

			cnt[i]+=cnt[i-1];

		int ans=0;

		for(register int i=n;i>=1;--i)

			if(cnt[i]>cnt[ans])

				ans=i;

		if(ans)

			write(ans),puts("");

		else

			puts("-1");

	}

	return 0;

}