自动搬运

查看原文

来自洛谷，原作者为

	teafrogsf 这个家伙很弱，什么也没有留下。

搬运于2025-08-24 21:55:39，当前版本为作者最后更新于2018-06-12 21:07:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

$60pts:$
有一个常见的套路是：看见序列分段想$\Theta(n^2)DP+$优化。
这题目要的是$L$的最大值，那么不影响我们$DP$的结果，可以直接二分答案。
这个分段的$DP$也是很显然，设$dp_i$表示以i作为当前段结尾：

$$dp_i=\max(dp_j+i-(j+1)+1,dp_{i-1}),j\in [i-maxlen_i,i-l] $$

其中，$maxlen_i$表示以$i$为结尾的字符串出现在模板串中的最长长度，这个可以用$SAM$一开始跑出来；$l$表示当前二分的答案。
这样我们得到了（上界复杂度）$O(n^2\log n)$的算法。

$100pts:$
决策单调性很显然，因为$i-maxlen_i$一定是单调递增的。
发现决策单调性之后，将$dp$方程改成$dp_j-j+i$，$i$显然单调递增，那么就可以维护前面这个$dp_j-j$的单调递减队列了。复杂度$O(n\log n)$。
$P.S.$其实没有必要用广义$SAM$的，只要隔一个字符插就可以了，虽然空间貌似有那么一点儿......大？

#include<cstdio>
#include<cstring>
#include<deque>
#define neko 2000010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
typedef int arr[neko];
arr link,len,dp,maxlen,q;
int n,m,nex[neko][3];
namespace SAM
{
	int slen,cnt,cur,last;
	void find(char *s)
	{
		int p=0,now=0,x;
		slen=strlen(s+1);
		f(i,1,slen)
		{
			x=s[i]-'0';
			if(nex[p][x])++now,p=nex[p][x];
			else
			{
				for(;p!=-1&&(!nex[p][x]);p=link[p]);
				if(p==-1)p=0,now=0;
				else now=len[p]+1,p=nex[p][x];
			}maxlen[i]=now;
		}
	}//this is right
	void extend(char *s)
	{
		int p,q,clone,x;
		link[0]=-1,slen=strlen(s+1);s[++slen]='2';
		f(i,1,slen)
		{
			cur=++cnt,len[cur]=len[last]+1;
			x=s[i]-'0';
			for(p=last;p!=-1&&(!nex[p][x]);p=link[p])nex[p][x]=cur;
			if(p==-1)link[cur]=0;
			else
			{
				q=nex[p][x];
				if(len[p]+1==len[q])link[cur]=q;
				else
				{
					clone=++cnt;
					len[clone]=len[p]+1;
					link[clone]=link[q];
					f(j,0,1)nex[clone][j]=nex[q][j];
					for(;p!=-1&&(nex[p][x]==q);p=link[p])nex[p][x]=clone;
					link[q]=link[cur]=clone;
				}
			}last=cur;
		}
	}
}
bool check(int l)
{
	int slen=SAM::slen,j,H=0,T=-1;
	//easily(?) to prove that it has a monotonicity of decision making
	f(i,0,l-1)dp[i]=0;
	f(i,l,slen)
	{
		dp[i]=dp[i-1];
		while(H<=T&&(dp[i-l]-(i-l))>(dp[q[T]]-q[T]))--T;
		q[++T]=i-l;
		while(H<=T&&q[H]<(i-maxlen[i]))++H;
		if(H<=T)dp[i]=chkmax(dp[i],dp[q[H]]-q[H]+i);//i-(j+1)+1
		//f(j,i-maxlen[i],i-l)if(dp[j]+(i-j)>dp[i])dp[i]=dp[j]+(i-j);//i-(maxlen[i]+1)+1
	}//f(i,1,slen)printf("%d ",dp[i]);puts("");
	return dp[slen]*10>=slen*9;
}
char s[neko];
#define mid ((l+r)>>1)
int main()
{
	using namespace SAM;
	int l,r;
	scanf("%d%d",&n,&m);
	f(i,1,m)scanf("%s",s+1),extend(s);
	f(i,1,n)
	{
		scanf("%s",s+1);
		l=1,r=strlen(s+1);
		find(s);
		while(l<=r)
		{
			//printf("%d %d %d\n",l,r,mid);
			if(check(mid))l=mid+1;
			else r=mid-1;
		}printf("%d\n",mid);
	}return 0;
}