题解 P4770 【[NOI2018]你的名字】

2020-01-03 12:13:59


最近一直在学后缀自动机。。。。

感觉这道题很不错。。。。然后发现不会做(捂脸)

感觉这个去重的方法非常的厉害

所以来写一篇题解,成为我后缀自动机的第一篇题解

Part1

首先考虑l=1,并且r=n的怎么做(不考虑去重)

就是对S建后缀自动机,让T对他跑匹配

如果有字符直接跳,并让l++;没有的话跳parent,并让l=maxlen(l),如果为0就重新开始

这个可以l表示对于T中每一个前缀1...i的可以匹配到的最长后缀长度

那么用sigma(i-l) 就是答案(当然没有考虑去重)

Part2

考虑如果l,r任意的话怎么做。这次就没有方法直接转移了,因为你不知道你的这个节点所表示出的串是不是在l-r的范围内

那么我们用线段树合并维护对于每一个节点的所有endpos的值

在跳的时候就是看转移到下一个的内个字符的endpos集合是不是有在(L+l,R)这个区间内部的,如果有的话,就转移

但是失配了怎么办。。。那就让l--,含义就相当与是在已经匹配好的后缀删除第1个字符(注意不能直接跳到parent上,因为可能删除一个字符endpos就可以满足了),如果删除到和他(parent的len==l) 的话就得跳parent了。

Part3

去重。。。。考虑对T建自动机

对那么根据本质不同字串做法就是len(i)-len(fa)

但是要减去相同的

就是len(i)-(max(len(fa),和可以与S匹配的最大值))的和

那么我们把刚刚的内个l放到节点上我们显然不可以把它放到前缀上暴力跳parent(但是据说复杂度也是对的)

所以我们考虑在建自动机的时候除了分裂出的节点都是前缀。。。 所以我们只需要考虑分裂出来的节点

我们知道分裂出来的节点nq是np和q的parent,也就是他们的后缀

我们考虑用谁来继承发现都可以!!!因为nq被q和np完全包涵

所以直接用q的和np的任意一个来给nq就可以了(不懂的要好好思考这一步)

好了,就这些,这题就解决了。。。(如果有错误请指出,谢谢)

代码,完结撒花

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
    return x*f;
}

const int maxn=1e6+5;

#define mid ((l+r)>>1)

int node_cnt,ls[maxn<<5],rs[maxn<<5],n,m;
int siz[maxn<<5],root[maxn],A[maxn],mx[maxn];
char s[maxn],T[maxn];

struct xx{
    int las=1,tot=1,t[maxn];
    struct node{
        int len,fa,ch[26];
    }dian[maxn];
    inline void modify(int c){
        int p=las,np=las=++tot;dian[np].len=dian[p].len+1;
        for(;p&&!dian[p].ch[c];p=dian[p].fa) dian[p].ch[c]=np;
        if(!p) dian[np].fa=1;
        else{
            int q=dian[p].ch[c];
            if(dian[q].len==dian[p].len+1) dian[np].fa=q;
            else{
                int nq=++tot;dian[nq]=dian[q];dian[nq].len=dian[p].len+1;
                dian[q].fa=dian[np].fa=nq;
                for(;p&&dian[p].ch[c]==q;p=dian[p].fa) dian[p].ch[c]=nq;
            }
        }
    }
    inline void Qsort(){
        for(int i=1;i<=tot;i++) t[dian[i].len]++;
        for(int i=1;i<=n;i++) t[i]+=t[i-1];
        for(int i=tot;i>=1;i--) A[t[dian[i].len]--]=i;
    }
}SA1;

struct xxx{
    int las=1,tot=1,tag[maxn<<1];
    struct node{
        int len,fa,ch[26];
    }dian[maxn<<1];
    inline void clear(){
        for(int i=1;i<=tot;i++){
            dian[i].len=dian[i].fa=0;
            for(int j=0;j<26;j++) dian[i].ch[j]=0;
            tag[i]=0;
        }
        las=tot=1;
    }
    inline void modify(int c,int id){
        int p=las,np=las=++tot;dian[np].len=dian[p].len+1;tag[np]=id;
        for(;p&&!dian[p].ch[c];p=dian[p].fa) dian[p].ch[c]=np;
        if(!p) dian[np].fa=1;
        else{
            int q=dian[p].ch[c];
            if(dian[q].len==dian[p].len+1) dian[np].fa=q;
            else{
                int nq=++tot;dian[nq]=dian[q];dian[nq].len=dian[p].len+1;tag[nq]=tag[np];
                dian[q].fa=dian[np].fa=nq;
                //当然用tag[nq]=tag[q]也对啊
                for(;p&&dian[p].ch[c]==q;p=dian[p].fa) dian[p].ch[c]=nq;
            }
        }
    }
}SA2;

inline void insert(int &x,int l,int r,int pos){
    if(!x) x=++node_cnt;siz[x]++;
    if(l==r) return;
    if(pos<=mid) insert(ls[x],l,mid,pos);
    else insert(rs[x],mid+1,r,pos);
}

inline int merge(int x,int y){
    if(!x||!y) return x+y;
    int z=++node_cnt;siz[z]=siz[x]+siz[y];
    ls[z]=merge(ls[x],ls[y]);
    rs[z]=merge(rs[x],rs[y]);
    return z;
}

inline int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return siz[x];
    int ans=0;
    if(L<=mid) ans+=query(ls[x],l,mid,L,R);
    if(R>mid) ans+=query(rs[x],mid+1,r,L,R);
    return ans;
}

int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++) SA1.modify(s[i]-'a'),insert(root[SA1.las],1,n,i);
    SA1.Qsort();
    for(int i=SA1.tot;i>=1;i--) root[(SA1.dian[A[i]].fa)]=merge(root[(SA1.dian[A[i]].fa)],root[A[i]]);
    int tim=read();
    while(tim--){
        SA2.clear();scanf("%s",T+1);m=strlen(T+1);
        for(int i=1;i<=m;i++) SA2.modify(T[i]-'a',i);
        for(int i=1;i<=SA2.tot;i++) mx[i]=0;
        int cur=1,l=0;long long ans=0;
        int L=read(),R=read();
        for(int i=1;i<=m;i++){
            while(1){
                if((SA1.dian[cur].ch[T[i]-'a'])&&(query(root[SA1.dian[cur].ch[T[i]-'a']],1,n,L+l,R))){
                    cur=SA1.dian[cur].ch[T[i]-'a'];l++;
                    break;
                }
                if(l==0) break;
                l--;
                if(l==SA1.dian[SA1.dian[cur].fa].len) cur=SA1.dian[cur].fa;
            }
            mx[i]=l;
        }
        for(int i=2;i<=SA2.tot;i++){
            ans+=max(0,SA2.dian[i].len-max(SA2.dian[SA2.dian[i].fa].len,mx[SA2.tag[i]]));
        }
        printf("%lld\n",ans);
    }
    return 0;
}