2806: [Ctsc2012]Cheat
Time Limit: 20 Sec
Memory Limit: 256 MB
Submit: 1324
Solved: 676
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
【分析】
后缀自动机+单调队列优化DP
手玩了很长时间...终于玩出来单调队列优化DP了...唉单调队列真的学成shi了。
首先我们可以把标准作文库里的串建一个广义后缀自动机...然后用作文串在自动机上匹配，用mat[i]表示作文串以第i个字符为结尾的最大匹配长度。
由于L不好直接求出，我们可以二分答案，假设当前二分的答案是L0，用dp[i]表示作文串前i个字符能匹配的最长长度，那么对于每个i，dp[i]=max{dp[j]+j-i}(i-mat[i]<=j<=i-L0)
观察到i-mat[i]有一个神奇的性质：单调不减。因为mat[i]+1>=mat[i+1]，所以 i+1-mat[i+1]>=i-mat[i] 。满足决策单调性...所以用一个单调队列维护一个dp[j]-j单调减的数列，然后跑就好啦。
【代码】
//CTSC 2012 Cheat
#include<iostream>
#include<cstring>
#include<cstdio>
#define eps 1e-3
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int mxn=2200005;
char s[mxn>>1];
int n,m,p,np,q,nq,tot,len,root;
int son[mxn][2],pre[mxn],step[mxn],mat[mxn>>1],dp[mxn>>1],Q[mxn>>1];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
inline void sam(int c)
{
p=np;
step[np=(++tot)]=step[p]+1;
while(p && !son[p][c])
son[p][c]=np,p=pre[p];
if(!p) {pre[np]=1;return;}
q=son[p][c];
if(step[q]==step[p]+1) {pre[np]=q;return;}
step[nq=(++tot)]=step[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
pre[nq]=pre[q];
pre[q]=pre[np]=nq;
while(p && son[p][c]==q)
son[p][c]=nq,p=pre[p];
}
inline void find()
{
p=root;
fo(i,1,len)
{
int c=s[i]-'0';
if(son[p][c]) mat[i]=mat[i-1]+1,p=son[p][c];
else
{
while(p && !son[p][c])
p=pre[p];
if(son[p][c]) mat[i]=step[p]+1,p=son[p][c];
}
}
}
inline bool ok(int L)
{
int h=1,t=1;
Q[1]=0;
fo(i,1,len)
{
dp[i]=dp[i-1];
while(h<=t && Q[h]<i-mat[i]) h++;
if(Q[h]<=i-L && h<=t)
dp[i]=max(dp[i],dp[Q[h]]+i-Q[h]);
while(h<=t && i-L+1>=1 && dp[i-L+1]-(i-L+1)>=dp[Q[t]]-Q[t]) t--;
if(i-L+1>=1) Q[++t]=i-L+1;
}
return (double)dp[len]>(double)len*0.9-eps;
}
inline int work()
{
int l=0,r=len;
while(l<r)
{
int mid=(l+r>>1)+1;
if(ok(mid)) l=mid;
else r=mid-1;
}
return l;
}
int main()
{
n=read(),m=read();
np=root=tot=1;
fo(i,1,m)
{
np=1;
scanf("%s",s+1);
len=strlen(s+1);
fo(i,1,len)
sam(s[i]-'0');
}
while(n--)
{
scanf("%s",s+1);
len=strlen(s+1);
find();
printf("%d\n",work());
}
return 0;
}