2806: [Ctsc2012]Cheat
题意：
多个主串和多个询问串，每次询问将询问串分成多个连续子串，如果一个子串长度>=L且在主串中出现过就是熟悉的
如果熟悉的字符串长度>=询问串长的90%就是熟悉的文章；求成为熟悉的文章的最大的L
主串建广义SAM然后二分L判断可行性
使用DP判断L是否可行，一定要注意是长度不是数量，煞笔Candy?就看错题了
len[i]表示i位置之前最大公共长度，和spoj LCS一样...
f[i]表示前i个字符最长熟悉长度，f[i]=max{f[i-1],f[j]+j-i|i-len[i]<=j<=i-L}，显然i-len[i]不严格递增，使用单调队列优化到O(n)
DP注意：
1.f[i-1]这个转移
2.判断条件i-L<0说明没有转移；0也是一个转移！！但不能一开始先把0加入队列WA了好多次
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=1e6+;
typedef long long ll;
int n,m;
char s[N];
struct node{
int ch[],par,val;
}t[N];
int sz=,root=,last=;
void extend(int c){
int p=last,np=++sz;
t[np].val=t[p].val+;
for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;
if(!p) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=++sz;
t[nq]=t[q];t[nq].val=t[p].val+;
t[q].par=t[np].par=nq;
for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;
}
}
last=np;
}
int len[N],f[N];
void getLen(){
int u=root,sum=;
for(int i=;i<=n;i++){
int c=s[i]-'';
if(t[u].ch[c]) u=t[u].ch[c],sum++;
else{
while(u&&!t[u].ch[c]) u=t[u].par;
if(!u) u=root,sum=;
else sum=t[u].val+,u=t[u].ch[c];
}
len[i]=sum;//printf("len %d %d\n",i,len[i]);
}
}
int q[N],head,tail;
bool check(int L){//printf("L %d\n",L);
head=;tail=;
for(register int i=;i<=n;i++){
f[i]=f[i-];
if(i-L<) continue;
while(head<=tail&&f[q[tail]]-q[tail]<f[i-L]-i+L) tail--;
q[++tail]=i-L;
while(head<=tail&&q[head]<i-len[i]) head++;
if(head<=tail) f[i]=max(f[i],f[q[head]]+i-q[head]);
//printf("f %d %d\n",i,f[i]);
}
//printf("f %d %d\n",n,f[n]);
return f[n]*>=n*;
}
void solve(){
getLen();
int l=,r=n,ans=;
while(l<=r){
int mid=(l&r)+((l^r)>>);
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
int main(){
freopen("in","r",stdin);
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++){
scanf("%s",s+);
int len=strlen(s+);
last=root;
for(int j=;j<=len;j++) extend(s[j]-'');
}
for(int i=;i<=m;i++){
scanf("%s",s+);
n=strlen(s+);
solve();
}
}