正题

题目链接:https://www.luogu.com.cn/problem/P4022

题目大意

给出\(m\)个模板串。

然后\(n\)次询问给出一个串\(S\)要求找到一个最大的\(L\)使得能够将\(S\)超过\(90\%\)的部分拿出来分后每个串都是某个模板串的子串且长度不小于\(L\)。

所有输入文件长度不超过 \(1100000\) 字节。字符集为\(\{0,1\}\)

解题思路

先把模板串拿出来构一个广义SAM，然后考虑用这个对串进行匹配。

先对于每个位置求出一个\(len_i\)表示一个最长的长度使得\(i\)的后缀是某个模板串的子串。

然后考虑二分一个\(L\)后进行\(dp\)。

那么有

\[f_i=max\{f_{i-1},f_j+i-j\}(\ j\in[i-len_i,i-L)\ )
\]

因为\(i-len_i\)单调所以把\(j\)丢进单调队列里就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1200000;

int n,m,cnt,f[N],q[N],ml[N];

int ch[N][2],len[N],fa[N];

char s[N];

int Insert(int p,int c){

	if(ch[p][c]){

		int q=ch[p][c];

		if(len[p]+1==len[q])return q;

		else{

			int nq=++cnt;len[nq]=len[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[nq]));

			fa[nq]=fa[q];fa[q]=nq;

			for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;

			return nq;

		}

	}

	int np=++cnt;len[np]=len[p]+1;

	for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

	if(!p)fa[np]=1;

	else{

		int q=ch[p][c];

		if(len[p]+1==len[q])fa[np]=q;

		else{

			int nq=++cnt;len[nq]=len[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[nq]));

			fa[nq]=fa[q];fa[q]=fa[np]=nq;

			for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;

		}

	}

	return np;

}

bool check(int L,int n){

	int head=1,tail=0,ans=0;

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

		if(i>=L){

			int j=i-L;

			while(head<=tail&&f[j]-j>f[q[tail]]-q[tail])tail--;

			q[++tail]=j;

		}

		while(head<=tail&&q[head]<i-ml[i])head++;

		f[i]=0;

		if(head<=tail)f[i]=f[q[head]]+i-q[head];

		f[i]=max(f[i],f[i-1]);

		ans=max(ans,f[i]);

	}

	return (ans*10>=n*9);

}

int main()

{

	scanf("%d%d",&n,&m);cnt=1;

	for(int i=1;i<=m;i++){

		scanf("%s",s+1);

		int l=strlen(s+1),x=1;

		for(int j=1;j<=l;j++)

			x=Insert(x,s[j]-'0');

	}

	while(n--){

		scanf("%s",s+1);

		int sl=strlen(s+1),x=1,L=0;

		for(int i=1;i<=sl;i++){

			int c=s[i]-'0';

			while(x&&!ch[x][c])

			{x=fa[x];L=len[x];}

			if(x)x=ch[x][c],L++;

			else x=1,L=0;

			ml[i]=L;

		}

		int l=1,r=sl;

		while(l<=r){

			int mid=(l+r)>>1;

			if(check(mid,sl))l=mid+1;

			else r=mid-1;

		}

		printf("%d\n",r);

	}

	return 0;

}

巴特西

P4022-[CTSC2012]熟悉的文章【广义SAM,dp,单调队列】

正题

题目大意

解题思路

code

最新文章

热门文章