DZY 's BLOG

求两个串的最长公共子串。串长250000。

很像上一道题处理d[i]数组。

给第一个串建后缀自动机。

第二个串在上面跑即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510010;
char buf[maxn],*pt=buf;
int l[maxn],fa[maxn],c[maxn][26],rt=1,tot=1,tail=1;
void add(int x){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!c[p][x];p=fa[p])   c[p][x]=np;
    if(!p){ fa[np]=rt;   return;}
    if(l[p]+1==l[q=c[p][x]]){   fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(c[r],c[q],sizeof(c[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&c[p][x]==q;p=fa[p]) c[p][x]=r;
}int main(){
    fread(buf,1,510000,stdin);  char ch;
    while((ch=*pt++)!='\n') add(ch-'a');
    int p=rt,k=0,x,An=0;    
    while((ch=*pt++)!='\n'){
        if(c[p][x=ch-'a'])    ++k,p=c[p][x],An=max(k,An); else{
            for(;p&&!c[p][x];p=fa[p]);
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=c[p][x],An=max(k,An);
        }
    }printf("%d\n",An); return 0;
}

二分+后缀自动机还是比较好想的。dp优化只能膜拜题解了。==

题意：给定一些01字符串作为标准作文库。然后给你几篇作文。对于每篇作文，把这篇作文分成若干段后，如果一段的长度不小于L，且是标准作文库中某个字符串的连续子串，这样这一段作文就是匹配的。求L的最大值，使得这篇作文的90%是匹配的。

一眼看出是二分+判定。因为如果L0可行，那小于L0的L都可行。

然后就可以考虑如何判定。分段的话应该是要dp了。设这个作文是S。

先预处理出一个数组d[i],d[i]=max{i-j+1|S[j..i]是标准作文库中某个字符串的连续子串}

这个用后缀自动机。把标准作文库里的所有字符串拼起来。中间加一个分隔符2好了。然后O(n)建后缀自动机。

然后让S在自动机上跑。

跑的过程具体就是：从root开始，如果下一个字符可以转移就转移，更新len值，如果不能就一直回退直到可以转移，回到根了那len=0，如果还没到根，len=当前结点的l值，并且继续转移。

定义数组f[i]为S[1..i]匹配的最大长度。则f[i]=max{f[j]+i-j|i-d[i]<=j<=i-L}。可惜这样dp是O(n^2)的承受不起。

优化：

f[i]=i+max{f[j]-j|i-d[i]<=j<=i-L}。然后令g[j]=f[j]-j。

考虑它的决策区间。

首先i-d[i]是非严格递增的。

如果有某个i，使得i-d[i]>i+1-d[i+1]，由d[i]的意义知S[i-d[i]+1..i]和S[i+1-d[i+1]+1..i+1]是字典中某个串的子串。
由于i-d[i]+1>i+1-d[i+1]+1，知S[i+1-d[i+1]+1..i]也是字典中某个串的子串且比S[i-d[i]+1..i]更长，这与d[i]的定义中的max违背。

i-L是严格递增的。显然。

那么[i-d[i],i-L]只会右移。那么用g[]递减的一个单调队列维护决策区间即可。

最后的复杂度应该是O(nlogn)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1100010;
int l[maxn],ch[maxn][3],d[maxn],f[maxn],g[maxn],q[maxn],fa[maxn];
int rt=1,tail=1,tot=1,n,len;    char s[maxn];
void add(int c){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!ch[p][c];p=fa[p])  ch[p][c]=np;
    if(!p){ fa[np]=rt;  return;}
    if(l[p]+1==l[q=ch[p][c]]){  fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(ch[r],ch[q],sizeof(ch[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&ch[p][c]==q;p=fa[p])    ch[p][c]=r;
}void init(){
    int p=rt,k=0,x;
    for(int i=1;i<=n;i++){
        if(ch[p][x=s[i]-48])    k++,    p=ch[p][x]; else{
            while(p&&!ch[p][x]) p=fa[p];
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=ch[p][x];
        }d[i]=k;
    }
}int mt(int r){
    int s=1,e=0,t;
    for(int i=1;i<=n;i++){
        if((t=i-r)>=0){
            while(s<=e&&g[q[e]]<g[t])   e--;
            q[++e]=t;
        }while(s<=e&&q[s]<i-d[i])    s++;
        f[i]=f[i-1];
        if(s<=e&&f[i]<g[q[s]]+i)    f[i]=g[q[s]]+i;
        g[i]=f[i]-i;
    }return f[n]>=len;
}int main(){
    int tc,m;   scanf("%d%d",&tc,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        int k=strlen(s+1);
        for(int j=1;j<=k;j++)    add(s[j]-48);
        if(i!=m)add(2);
    }while(tc--){
        scanf("%s",s+1);    n=strlen(s+1);
        len=(int)(ceil((double)n*0.9));
        init(); if(!mt(1)){   printf("0\n");  continue;}
        int L=2,R=n,mid;
        while(L<=R){
            mid=(L+R)>>1;
            if(mt(mid)) L=mid+1;    else    R=mid-1;
        }printf("%d\n",R);
    }return 0;
}