2806: [Ctsc2012]Cheat
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 583 Solved: 330
[Submit][Status][Discuss]
Description
Input
第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库
的行数
接下来M行的01串，表示标准作文库
接下来N行的01串，表示N篇作文
Output
N行，每行一个整数，表示这篇作文的Lo 值。
Sample Input
1 2
10110
000001110
1011001100
10110
000001110
1011001100
Sample Output
4
HINT
输入文件不超过1100000字节
注意：题目有改动,可识别的长度不小于90%即可，而不是大于90%
先将作文库建后缀自动机，多篇文章可以通过在中间加入分隔符来完成。对于每组询问，预处理出每一个位置向前最多匹配多长g[]。
二分答案len，dp[]表示匹配到当前位置的最多匹配数，对于i位置，dp[i]由一段通过len，与g确定出的区间[l,r]转移，本来用了一个线段树维护，但是由于时间复杂度O(n*log^2n)，TLE了，观察发现[l,r]是单调的，故可直接用单调队列。
网上一半题解过不了数据：1 1 1 1
另外，对于0.9的问题确实说明了以后能用int就不要用double，实在不行要加eps。
省选前最后一题了，真觉得时间过得太快了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 4100000
#define MAXT MAXN*4
#define INF 0x3f3f3f3f
#define lch (now<<1)
#define rch (now<<1^1)
#define smid ((l+r)>>1)
char buf[MAXN];
char *bufnow(buf);
int len[MAXN];
char *str[MAXN];
char buf2[MAXN];
char *bufnow2(buf2);
struct sam_node
{
int nxt[];
int pnt,len;
void Print()
{
for (int i=;i<;i++)
printf("%d[%d] ",i,nxt[i]);
printf("\n");
printf("Pnt:%d\n",pnt);
}
}sam[MAXN];
int tops=;
int last=;
void Add_item(int w)
{
int p=last;
int np=++tops;
sam[np].len=sam[p].len+;
while (p && !sam[p].nxt[w])
sam[p].nxt[w]=np,p=sam[p].pnt;
if (!p)
{
last=np;
sam[np].pnt=;
}else
{
int q=sam[p].nxt[w];
if (sam[p].len+==sam[q].len)
{
sam[np].pnt=q;
}else
{
int nq=++tops;
sam[nq]=sam[q];
sam[nq].len=sam[p].len+;
sam[nq].pnt=sam[q].pnt;
sam[q].pnt=nq;
sam[np].pnt=nq;
while (p && sam[p].nxt[w]==q)
{
sam[p].nxt[w]=nq;
p=sam[p].pnt;
}
}
}
last=np;
}
int g[MAXN];
int dp[MAXN];
int seq[MAXN]; int main()
{
freopen("input.txt","r",stdin);
int n,m;
int x,y;
scanf("%d%d\n",&n,&m);
for (int i=;i<m;i++)
{
scanf("%s\n",bufnow2);
bufnow2+=strlen(bufnow2);
*(bufnow2++)='';
}
for (int i=;i<n;i++)
{
scanf("%s\n",bufnow);
str[i]=bufnow;
bufnow+=len[i]=strlen(bufnow);
bufnow++;
}
for (char *i=buf2;i!=bufnow2;i++)
{
Add_item(*i-'');
}
for (int i=;i<=tops;i++)
{
// printf("SAM<%d>:\n",i);
// sam[i].Print();
}
for (int i=;i<n;i++)
{
int now=;
int clen=;
for (int j=;j<len[i];j++)
{
int w=str[i][j]-'';
if (sam[now].nxt[w])
{
now=sam[now].nxt[w];
clen++;
}else
{
while (now && !sam[now].nxt[w])
now=sam[now].pnt;
if (!now)
{
now=;
clen=;
}else
{
clen=sam[now].len+;
now=sam[now].nxt[w];
}
}
g[j]=clen;
// printf("%d\n",clen);
}
for (int j=len[i];j>=;j--)
g[j]=g[j-];
g[]=;
int l=,r=len[i]+;
int mid;
int head,tail=;
int ny;
while (l+<r)
{
mid=(l+r)>>;
int t;
for (int j=;j<=len[i];j++)
dp[j]=-INF;
dp[]=;
head=,tail=-;
ny=;
for (int j=;j<=len[i];j++)
{
x=j-g[j];
y=j-mid;
while (ny<=y)
{
while (head<=tail && dp[seq[tail]]<=dp[ny])
tail--;
seq[++tail]=ny++;
}
while (head<=tail && seq[head]<x)
head++;
dp[j]=dp[j-]+(j-);
if (head<=tail)
dp[j]=max(dp[j],dp[seq[head]]+j);
dp[j]-=j;
}
t=dp[len[i]]+len[i];
if (t*>=len[i]*)
l=mid;
else
r=mid;
}
printf("%d\n",l);
}
}