bzoj 2806: [Ctsc2012]Cheat （字尾自動機+dp+單調隊列）

2806: [Ctsc2012]Cheat

Time Limit: 20 Sec   Memory Limit: 256 MB

Submit: 1056   Solved: 544

[ Submit][ Status][ Discuss]

Description

Input

第一行兩個整數N，M表示待檢查的作文數量，和小強的标準作文庫

的行數

接下來M行的01串，表示标準作文庫

接下來N行的01串，表示N篇作文

Output

N行，每行一個整數，表示這篇作文的Lo 值。

Sample Input

1 2

10110

000001110

1011001100

Sample Output

4

HINT

輸入檔案不超過1100000位元組

注意：題目有改動,可識别的長度不小于90%即可，而不是大于90%

Source

[ Submit][ Status][ Discuss]

題解：字尾自動機+dp+單調隊列

對标準作文庫建立廣義的字尾自動機，然後處理作文的時候先讓其在字尾自動機上進行比對。求出對于作文中的每個位置最長比對的長度ans[i]（就是從這個點向前最多多長是标準作文庫的子串）

然後我們可以二分L，然後判定。

f[i]表示的到i最長的比對長度 f[i]=max(f[i-1],f[j]+i-j) i-ans[i]<=j<=i-L

這個dp是O(n^2)的 ，但是我們必須要降為O(n)

ans[i]+1>=ans[i+1]

i+1-ans[i]-1<=i+1-ans[i+1]

i-ans[i]<=i+1-ans[i+1]

是以i-ans[i]是單調不降的，我們可以用單調隊列維護區間f[i]-i的最值。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define N 1100003
#define eps 1e-7
using namespace std;
int l[N],ch[N][3],fa[N],ans[N],st[N],top,f[N];
int n,m,cnt,root,last,size,p,q,np,nq,pos[N],cn;
char s[N],s1[N];
struct data{
	int l,r,len;
}a[N];
int cmp(data a,data b)
{
	return a.l<b.l||a.l==b.l&&a.r<b.r;
}
void extend(int i)
{
    int x=s1[i]-'0';
	p=last; last=np=++size;
	l[np]=l[p]+1;
	for (;!ch[p][x]&&p;p=fa[p]) ch[p][x]=np;
	if (!p) fa[np]=root;
	else {
		q=ch[p][x];
		if (l[p]+1==l[q]) fa[np]=q;
		else {
			nq=++size; l[nq]=l[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[nq]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			for (;ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
		}
	}
}
void solve()
{
	p=root; int tmp=0;
	for (int i=1;i<=cnt;i++) {
		int x=s[i]-'0';
		if (ch[p][x]!=0) 
		  tmp++,p=ch[p][x];
		else {
			while (!ch[p][x]&&p) p=fa[p];
			if (!p) p=root,tmp=0;
			else tmp=l[p]+1,p=ch[p][x]; 
		}
		ans[i]=tmp;
	}
}
bool pd(int len)
{
	if (len==0) return true;
	int head=1,tail=0;
	f[0]=0; 
	for (int i=1;i<=cnt;i++) {
		f[i]=f[i-1];
		int pos=i-len;
		if (pos>=0){		 
		  while (f[st[tail]]-st[tail]<f[pos]-pos&&head<=tail)  tail--;
		  st[++tail]=pos;
		}
		while (head<=tail&&st[head]<i-ans[i]) head++;
		if (head<=tail) f[i]=max(f[i],f[st[head]]-st[head]+i);
	}
	if ((double)f[cnt]*1.0>=(double)cnt*0.9-eps) return true;
	else return false;
}
int main()
{
   freopen("a.in","r",stdin);
   freopen("my.out","w",stdout);
   scanf("%d%d",&n,&m);
   root=size=1;
   for (int i=1;i<=m;i++) {
   	 scanf("%s",s1+1);
   	 last=root;
   	 int len=strlen(s1+1);
   	 for (int j=1;j<=len;j++) 
		 extend(j);
   }
   for (int i=1;i<=n;i++) {
   	 scanf("%s",s+1);
   	 cnt=strlen(s+1);
     solve(); 
     cn=0; int l=0; int r=cnt;
   	 int ans1=0;
   	 while (l<=r) {
   	   int mid=(l+r)/2;
	   if (pd(mid)) ans1=max(ans1,mid),l=mid+1;
	   else r=mid-1;
	 }
	 printf("%d\n",ans1);
   }
}