[NOI 2018] 你的名字

UOJ #395.

思路

首先考虑一下满足“对于所有询问有$l=1,r=|S|$”时怎么做

很显然可以对$S$构建一个SAM,对于每个$T$也构建一个SAM,先对于$T$的每个位置求出与$S$中子串的最长公共后缀,然后到$T$的SAM上DP一下就可以了。寻找公共后缀的时候就一直跳parent,直到有我们需要的出边时停下,类似kmp。

现在加入了关于$l, r$的限制,受到限制的其实只有判断有没有需要的出边的时候。那么我们可以对于$S$的SAM上的每个节点开一棵线段树,维护一下right集合,自底向上进行一次线段树合并,那么我们的每个节点的线段树就是parent树上这个节点的子树中的节点的right集合的并集。然后只要查一下出边所指向的节点的线段树中是否包含$[l, r]$中的任何一个,就可以判断能不能走了

代码

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

typedef long long LL;

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

struct SegTree{
    struct Node{
        Node *lch, *rch;
        int val;
        Node() : lch(NULL), rch(NULL), val(0){}
    }*rt[1000010];
    
    void Modify(Node *&v, int l, int r, int p){
        if(!v) v=new Node();
        v->val++;
        if(l==r) return;
        int mid=(l+r)/2;
        if(p<=mid) Modify(v->lch, l, mid, p);
        else       Modify(v->rch, mid+1, r, p);
    }
    
    Node *Merge(Node *v1, Node *v2){
        if(!v1) return v2; if(!v2) return v1;
        Node *v=new Node();
        v->lch=Merge(v1->lch, v2->lch);
        v->rch=Merge(v1->rch, v2->rch);
        v->val=v1->val+v2->val;
        return v;
    }
    
    int Query(Node *v, int l, int r, int ql, int qr){
        if(!v) return 0;
        if(ql<=l && r<=qr) return v->val;
        int mid=(l+r)/2, ans=0;
        if(ql<=mid) ans+=Query(v->lch, l, mid, ql, qr);
        if(qr>mid)  ans+=Query(v->rch, mid+1, r, ql, qr);
        return ans;
    }
}St;

struct SAM{
    #define MX 2000010
    int cnt, end, fa[MX], ch[MX][26], len[MX], buc[MX], q[MX], l, id[MX];
    SAM() : cnt(1), end(1){}
    
    void insert(int c, int qwq){
        int p=end; end=++cnt; len[end]=len[p]+1; id[end]=qwq;
        for(int i=0; i<26; i++) ch[end][i]=0;
        for(; p && !ch[p][c]; p=fa[p]) ch[p][c]=end; 
        if(!p){fa[end]=1; return;}
        int q=ch[p][c];
        if(len[q]==len[p]+1){fa[end]=q; return;}
        cnt++; for(int i=0; i<26; i++) ch[cnt][i]=ch[q][i];
        fa[cnt]=fa[q]; fa[q]=fa[end]=cnt; len[cnt]=len[p]+1; id[cnt]=qwq;
        for(; p && ch[p][c]==q; p=fa[p]) ch[p][c]=cnt;
    }
    
    void build1(char *s){
        l=strlen(s+1);
        for(int i=1; i<=l; i++){
            insert(s[i]-'a', i);
            St.Modify(St.rt[end], 1, l, i);
        }
        std::fill(buc, buc+l+1, 0);
        for(int i=1; i<=cnt; i++) buc[len[i]]++;
        for(int i=1; i<=cnt; i++) buc[i]+=buc[i-1];
        for(int i=1; i<=cnt; i++) q[buc[len[i]]--]=i;
        for(int i=cnt; i>1; i--) 
            St.rt[fa[q[i]]]=St.Merge(St.rt[fa[q[i]]], St.rt[q[i]]);
    }
    
    void build2(char *s){
        l=strlen(s+1); memset(ch, 0, sizeof(ch[0])*(cnt+2)); cnt=end=1;
        for(int i=1; i<=l; i++) insert(s[i]-'a', i);
    }
}S, T;

char s[500010], t[1000010];
int lim[1000010];

int main(){
    int Q, l, r;
    scanf("%s", s+1);
    S.build1(s);
    in(Q);
    while(Q--){
        scanf("%s", t+1);
        in(l); in(r);
        T.build2(t);
        int v=1, tmp=0;
        for(int i=1; i<=T.l; i++){
            int c=t[i]-'a';
            while(1){
                if(!St.Query(St.rt[S.ch[v][c]], 1, S.l, l+tmp, r)){
                    if(!tmp) break; tmp--;
                    if(S.len[S.fa[v]]==tmp) v=S.fa[v];
                }else{tmp++; v=S.ch[v][c]; break;}
            }
            lim[i]=tmp;
        }
        LL ans=0;
        for(int i=2; i<=T.cnt; i++) ans+=std::max(0, T.len[i]-std::max(T.len[T.fa[i]], lim[T.id[i]]));
        printf("%lld\n", ans);
    }
    return 0;
}

发表评论

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