[BZOJ2806] [CTSC2012] Cheat

Description

Input

第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库
的行数
接下来M行的01串，表示标准作文库
接下来N行的01串，表示N篇作文

Output

N行，每行一个整数，表示这篇作文的Lo 值。

Sample Input

Sample Output

Solution

神题。

首先把模式串建出广义后缀自动机，由于我不会这个就只好把串用特殊符号连起来然后建单串(SAM)了...这玩意比较容易被卡的，这题字符集很小串长也很小就没啥问题。

然后对于匹配串预处理出一个(maxlen[i])表示第(i)位结尾的最长公共子串长度，这个可以在自动机上跑出来，具体的，沿着自动机走，如果走到了一个非法状态就条(parent)状态转移回去，然后长度就变成了(maxl+1)。

注意到(L)是满足可二分性的，所以可以先二分答案。

然后对于这种切成一段段的区间的问题可以考虑一个(O(n^2))的(dp)加玄学优化。

这里就设(f[i])表示考虑了前(i)个点的答案，然后可以得到一个很显然的转移：

[f[i]=max(f[i-1],max_{j=i-maxlen[i]}^{i-L}{f[j]+i-j}) ]

注意到决策点是单调不降的，并且(i)也是单增的，那么就可以用一个单调队列来维护(f[j]-j)。

时间复杂度(O(nlog n))。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

const int maxn = 2e6+10;

char s[maxn];
int n,m,qs=1,cnt=1,lstp=1,len,head,tail;
int par[maxn],tr[maxn][3],ml[maxn],mxlen[maxn],f[maxn];

void append(int c) {
	int p=lstp,np=++cnt;ml[np]=ml[p]+1;lstp=np;
	for(;p&&tr[p][c]==0;p=par[p]) tr[p][c]=np;
	if(!p) return par[np]=qs,void();
	int q=tr[p][c];
	if(ml[p]+1<ml[q]) {
		int nq=++cnt;ml[nq]=ml[p]+1;
		memcpy(tr[nq],tr[q],sizeof tr[nq]);
		par[nq]=par[q],par[q]=par[np]=nq;
		for(;p&&tr[p][c]==q;p=par[p]) tr[p][c]=nq;
	} else par[np]=q;
}

int q[maxn];

void get_mxlen() {
	int now=qs,res=0;
	for(int i=1,v;i<=len;i++) {
		if(tr[now][v=s[i]-'0']) now=tr[now][v],res++;
		else {
			for(;now&&tr[now][v]==0;now=par[now]);
			if(!now) now=qs,res=0;else res=ml[now]+1,now=tr[now][v];
		}
		mxlen[i]=res;
	}
}

int check(int L) {
	head=1,tail=0;
	for(int i=0;i<L;i++) f[i]=0;
	for(int i=L;i<=len;i++) {
		f[i]=f[i-1];
		while(head<=tail&&f[q[tail]]-q[tail]<f[i-L]-i+L) tail--;
		q[++tail]=i-L;
		while(head<=tail&&q[head]<i-mxlen[i]) head++;
		if(head<=tail) f[i]=max(f[i],f[q[head]]-q[head]+i);
	}return len*9<=f[len]*10;
}

int main() {
	read(n),read(m);
	for(int i=1;i<=m;i++) {
		scanf("%s",s+1);int l=strlen(s+1);append(2);
		for(int j=1;j<=l;j++) append(s[j]-'0');
	}
	for(int T=1;T<=n;T++) {
		scanf("%s",s+1);
		int l=0,r=strlen(s+1),mid,ans=0;
		len=r;get_mxlen();
		while(l<=r) if(check(mid=(l+r)>>1)) l=mid+1,ans=mid;else r=mid-1;
		write(ans);
	}
	return 0;
}