题解 P4022 【[CTSC2012]熟悉的文章】

· · 题解

没有发现决策单调性的蒟蒻用 n\log^2n 的算法莽过了这题

首先，我们可以预处理出来对于待考察的串中每个后缀，它与所有范文的后缀的 \operatorname{LCP} 的最长长度，记作 len 。

这个可以通过将所有串中间插上字符后并一起后缀排序，然后从每个位置向左向右扫到第一个范文后缀，在 O(n) 时间内得出。以下是求出 len_i 的代码：

for(int i=0,j=0;i<n;i++){
    j=min(j,ht[i]);
    if(id[sa[i]]>B)len[sa[i]]=max(len[sa[i]],j);
    if(id[sa[i]]&&id[sa[i]]<=B)j=n;
}
for(int i=n-1,j=0;i>=0;i--){
    if(id[sa[i]]>B)len[sa[i]]=max(len[sa[i]],j);
    if(id[sa[i]]&&id[sa[i]]<=B)j=n;
    j=min(j,ht[i]);
}

其中，id_i 是原串中每个后缀原本属于哪个串，id_i>B 就意味着来自于待考察串，而 1\leq id_i\leq B 则意为着来自范文串。

求出 len_i 后，我们便可以求出每个考察串的 L 了。显然，它具有单调性，于是可以二分。

那么这个二分如何check呢？我们考虑使用DP。

我们设 f_i 表示以 i-1 位置的字符结尾的前缀的串中，最多有多少个位置能够被判定为出现过。

我们发现，对于每个位置，都有一组范文串的备选集合。更准确地说，对于每个位置 i，如果 len_i\geq L，则区间 [i+L,i+len_i] 中所有位置都能接受到来自 i 开头的串。设 j 是该区间中的一个位置，则 f_j 可以由 f_i+j-i 转移过来。

显然这个 i+len_i 应该是单调不减的，因为如果 [i,i+len_i] 已经是一个合法串了，那么 [i+1,i+len_i] 就必然是一个合法串（它是前一个式子的子串）。这就可以用单调队列做到 O(n) DP。但是我没有意识到这一点，然后敲了个优先队列莽过去了。具体来说，把每个合法串的贡献以及它结束的位置丢入优先队列，要求值的时候只要堆顶元素所代表的串已经结束了就不断 pop。最后从堆顶元素转移即可。

以下是勉强卡过的代码（不保证再次提交仍可通过）：

#include<bits/stdc++.h>
using namespace std;
const int N=2301000;
int A,B,n,m,id[N],len[N],st[N],ed[N],f[N];
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],s[N];
char str[N];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        if(num>=n-1)break;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
struct node{
    int vl,ed;
    friend bool operator <(const node &x,const node &y){
        return x.vl<y.vl;
    }
    node(int x,int y){vl=x,ed=y;}
};
priority_queue<node>q;
bool che(int id,int ip){
    while(!q.empty())q.pop();
    f[st[id]-1]=0;
    for(int i=st[id];i<=ed[id];i++){
        f[i]=f[i-1];
        if(!(i-ip<st[id]||len[i-ip]<ip)){
            node x=node(f[i-ip]-(i-ip),i-ip+len[i-ip]);
            if(q.empty()||!(x.vl<=q.top().vl&&x.ed<=q.top().ed))q.push(x);
        }
        while(!q.empty()&&q.top().ed<i)q.pop();
        if(!q.empty())f[i]=max(f[i],i+q.top().vl);
    }
    return f[ed[id]]>=((ed[id]-st[id]+1)*9)/10;
}
void print(int x){
    if(x>9)print(x/10);
    putchar('0'+x%10);
} 
int main(){
    scanf("%d%d",&A,&B);
    for(int i=1;i<=A+B;i++){
        scanf("%s",str),m=strlen(str);
        st[i]=n;
        for(int j=0;j<m;j++)id[n]=i,s[n]=str[j]-'0'+1,n++;
        ed[i]=n;
        s[n++]=i+2;
    }
    m=A+B+2;
    SA();
    for(int i=0,j=0;i<n;i++){
        j=min(j,ht[i]);
        if(id[sa[i]]>B)len[sa[i]]=max(len[sa[i]],j);
        if(id[sa[i]]&&id[sa[i]]<=B)j=n;
    }
    for(int i=n-1,j=0;i>=0;i--){
        if(id[sa[i]]>B)len[sa[i]]=max(len[sa[i]],j);
        if(id[sa[i]]&&id[sa[i]]<=B)j=n;
        j=min(j,ht[i]);
    }
    for(int i=B+1;i<=A+B;i++){
        int l=0,r=ed[i]-st[i];
        while(l<r){
            int mid=(l+r+1)>>1;
            if(che(i,mid))l=mid;
            else r=mid-1;
        }
        print(l),putchar('\n');
    }
//  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",len[i]);puts("");
    return 0;
}