[CTSC 2012] 熟悉的文章

Luogu P4022

bzoj 2806

思路

考虑如果我们能求出$A$中以$i$结尾且在标准作文库内有匹配的最长一段的长度$g_i$,问题如何解决

这样的话就可以二分答案,并且DP来check,设$A_1\dots A_i$中“熟悉” 的子串的长度总和最多为$f_i$,则可列出以下的DP转移方程$$f_i=\max\{f_{i-1}, \max\limits_{i-g_i\leq j \leq i-L}\{f_j+i-j\}\}$$,很显然可以优先队列优化一下

然后我们来考虑如何求出$g_i$。可以拿所有的“标准作文库”中的串建一个广义SAM,然后只要拿串$A$在SAM里匹配,设$l$为当前匹配了的长度,$v$为上一个字符匹配到的SAM中的节点,如果$v$有$A_i$子节点的话就跳进$A_i$子节点,并令$l=l+1$,否则就不断令$v=fa_v$,直到$v$有$A_i$子节点或者跳到头不能继续跳,如果跳到头不能跳就令$l=0$,否则就令$l=len_v+1$,并让$v$跳进$A_i$字节点

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define mp std::make_pair

const int MX=1100000;
const double esp=1e-6;
int g[MX+10], f[MX+10];

namespace SAM{
    int len[MX*2+10], fa[MX*2+10], ch[MX*2+10][2], cnt=1;
    
    int insert(int c, int last){
        int p=last, end=++cnt; len[end]=len[p]+1; 
        for(; p && !ch[p][c]; p=fa[p]) ch[p][c]=end;
        if(!p){fa[end]=1; return end;}
        int q=ch[p][c];
        if(len[q]==len[p]+1){fa[end]=q; return end;}
        cnt++;
        for(int i=0; i<=1; i++) ch[cnt][i]=ch[q][i];
        fa[cnt]=fa[q]; fa[q]=cnt; fa[end]=cnt; len[cnt]=len[p]+1;
        for(; p && ch[p][c]==q; p=fa[p]) ch[p][c]=cnt;
        return end;
    }
    
    void work(char *s){
        int v=1, l=strlen(s+1), now=0;
        for(int i=1; i<=l; i++){
            if(!ch[v][s[i]-'0']){
                while(v && !ch[v][s[i]-'0']) v=fa[v];
                now=len[v];
            }
            if(!ch[v][s[i]-'0']) g[i]=now=0, v=1;
            else   g[i]=++now, v=ch[v][s[i]-'0'];
        }
        
    }
}

namespace Trie{
    struct Node{
        Node *ch[2];
        Node(){ch[0]=ch[1]=NULL;}
    }*root=new Node;
    
    void insert(char *s){
        int len=strlen(s+1);
        Node *v=root;
        for(int i=1; i<=len; i++){
            if(!v->ch[s[i]-'0']) v->ch[s[i]-'0']=new Node;
            v=v->ch[s[i]-'0'];
        }
    }
    
    void bfs(){
        std::queue<std::pair<int, Node *> >q;
        q.push(mp(1, root));
        while(!q.empty()){
            int last=q.front().first;
            Node *v=q.front().second;
            q.pop();
            for(int i=0; i<=1; i++) if(v->ch[i])
                q.push(mp(SAM::insert(i, last), v->ch[i]));
        }
    }
}
 int q[MX+10][2], h, t;
bool check(int L, int l){
    f[0]=0; h=1, t=0;
    for(int i=1; i<=l; i++){
        f[i]=f[i-1]; if(g[i]<L) continue;
        while(q[h][1]<i-g[i] && h<=t) h++;
        while(q[t][0]<f[i-L]-i+L && t>=h) t--;
        q[++t][0]=f[i-L]-i+L, q[t][1]=i-L;
        if(h<=t) f[i]=std::max(f[i], q[h][0]+i);
    }
    if((double)f[l]+esp>=0.9*l) return true;
    return false;
}

int main(){
    int N, M; char s[MX+10];
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; i++){
        scanf("%s", s+1); 
        Trie::insert(s);
    }
    Trie::bfs();
    while(N--){
        scanf("%s", s+1);
        SAM::work(s);
        int l=strlen(s+1);
        int L=0, R=MX, ans=0;
        while(L<=R){
            int mid=(L+R)/2;
            if(check(mid, l)) L=mid+1, ans=mid;
            else		   R=mid-1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注