2806: [Ctsc2012]Cheat
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 1262 Solved: 643Description
Input
第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库
的行数
接下来M行的01串，表示标准作文库
接下来N行的01串，表示N篇作文Output
N行，每行一个整数，表示这篇作文的Lo 值。
Sample Input
1 2
10110
000001110
1011001100Sample Output
4HINT
输入文件不超过1100000字节
注意：题目有改动,可识别的长度不小于90%即可，而不是大于90%
Source
【分析】
显然可以二分。
然后就是判断。
先用SAM找到i最长向左可以匹配的位置l，决策区间就是[i-l,i-lim]，思考一下发现这个决策区间是不断向右移动的，就是类似滑动窗口？这个就可以用单调队列了。
即f[i]=max{f[i-1],f[j]+j-i|i-l<=j<=i-lim}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 2500010 int mymax(int x,int y) {return x>y?x:y;} struct node
{
int son[],pre,step;
}t[Maxn*]; struct sam
{
int tot,last;
void extend(int k)
{
int np=++tot,p=last;
t[np].step=t[p].step+;
while(p&&!t[p].son[k])
{
t[p].son[k]=np;
p=t[p].pre;
}
if(!p) t[np].pre=;
else
{
int q=t[p].son[k];
if(t[q].step==t[p].step+) t[np].pre=q;
else
{
int nq=++tot;
memcpy(t[nq].son,t[q].son,sizeof(t[nq].son));
t[nq].step=t[p].step+;
t[nq].pre=t[q].pre;
t[q].pre=t[np].pre=nq;
while(p&&t[p].son[k]==q)
{
t[p].son[k]=nq;
p=t[p].pre;
}
}
}
last=np;
}
}sam; char s[Maxn]; int q[Maxn*];
int f[Maxn];
bool check(int x,int ll)
{
int l=,r=;
int nw=,sm=;
for(int i=;i<=ll;i++) f[i]=;
q[]=;
for(int i=;i<=ll;i++)
{
f[i]=f[i-];
int ind=s[i]-'';
while(nw&&!t[nw].son[ind]) nw=t[nw].pre,sm=t[nw].step;
if(t[nw].son[ind]) nw=t[nw].son[ind],sm++;
else {nw=;sm=;continue;}
while(i-x>=&&l<=r&&f[i-x]-(i-x)>f[q[r]]-(q[r])) r--;
if(i-x>=) q[++r]=i-x;
while(l<=r&&(q[l]<i-sm||q[l]>i-x)) l++;
if(l<=r) f[i]=mymax(f[i],f[q[l]]+i-q[l]);
}
return f[ll]*>=ll*;
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
sam.tot=sam.last=;
for(int i=;i<=m;i++)
{
scanf("%s",s);
int ll=strlen(s);
for(int j=;j<ll;j++) sam.extend(s[j]-'');
// sam.extend(2);
sam.last=;
}
for(int i=;i<=n;i++)
{
scanf("%s",s+);
int ll=strlen(s+);
int l=,r=ll;
while(l<r)
{
int mid=(l+r+)>>;
if(check(mid,ll)) l=mid;
else r=mid-;
}
printf("%d\n",l);
}
return ;
}
【打的是广义SAM？
2017-04-18 12:55:48