CF666E Forensic Examination

https://www.luogu.org/problemnew/show/CF666E

本質還是一個串在一些串裡的比對

考慮對模闆串建廣義SAM

既然有S的一些比對關系的詢問，套路地，

把S在上面跑，

pi[i]記錄S的[1~i]的字首在SAM上的比對長度

pos[i]記錄S的[1~i]的字首在SAM的比對最終位置

詢問的時候，如果比對長度不夠l，那麼輸出(L,0)

從pos[i]往上倍增，直到len剛好大于pr-pl+1（開始的時候，如果比對長度不夠，直接傳回0）

整個子樹對應的葉子就是所有出現位置。

沒有的話，還要檢查，輸出(L,0)

至于在[l,r]哪個串出現位置最多，線段樹合并即可。

或者dsu on the tree（即區間衆數） 拿兩個桶維護一下。

一個維護每個值出現次數，以及出現次數為某個次數的值有多少種。

代碼細節：

1.線段樹合并：由于之前的還要用，是以合并的時候務必建立一個節點，空間變成2倍，但是本質上參與合并的點數還是nlogn的。

否則類似主席樹，之前的值會改變，無法查詢！

2.記錄比對長度是在S的位置記錄！不是一般的在SAM上記錄最長比對位置！（這個簡直大錯特錯，因為可能和原子串根本不符合比對！長度大于，但是可能是S别的地方比對過來的！）

3.pi數組的長度是N，不是M（N,M）并不同階。

代碼：

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define mid ((l+r)>>1)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=5e5+5;
const int M=1e5+5;
int n,m;
char s[N],a[M];
pair<int,int> cmp(pair<int,int>a,pair<int,int>b){
    if(a.second==b.second) {
        return a.first<b.first?a:b;
    }    
    return a.second>b.second?a:b;
}
struct SAM{
    int f[2*M][20],ch[2*M][26],len[2*M];
    int nd,cnt;
    void init(){
        nd=cnt=1;
    }
    struct node{
        int ls,rs;
        int mx,id;
    }t[4*M*20];
    int rt[2*M];
    int pos[N];
    int pi[N];
    int num;
    void pushup(int x){
        if(t[t[x].ls].mx>t[t[x].rs].mx||(t[t[x].ls].mx==t[t[x].rs].mx&&t[t[x].ls].id<t[t[x].rs].id)){
            t[x].mx=t[t[x].ls].mx;
            t[x].id=t[t[x].ls].id;
        }
        else{
            t[x].mx=t[t[x].rs].mx;
            t[x].id=t[t[x].rs].id;
        }
    }
    void upda(int &x,int l,int r,int to,int c){
        if(!x) x=++num;
        if(l==r){
            t[x].mx+=c;t[x].id=l;return;
        }
        if(to<=mid) upda(t[x].ls,l,mid,to,c);
        else upda(t[x].rs,mid+1,r,to,c);
        pushup(x);
    }
    int merge(int x,int y,int l,int r){
        if(!x||!y) return x+y;
        int ret=++num;
        if(l==r){
            t[ret].mx=t[x].mx+t[y].mx;
            t[ret].id=t[x].id;
            return ret;
        }
        t[ret].ls=merge(t[x].ls,t[y].ls,l,mid);
        t[ret].rs=merge(t[x].rs,t[y].rs,mid+1,r);
        pushup(ret);
        return ret;
    }
    pair<int,int> query(int x,int l,int r,int L,int R){
        //cout<<" quering "<<l<<" "<<r<<" "<<L<<" "<<R<<" :: "<<t[x].id<<" "<<t[x].mx<<endl;
        if(L<=l&&r<=R){
            return make_pair(t[x].id,t[x].mx);
        }
        pair<int,int>ret;
        ret.first=0,ret.second=-2333;
        if(L<=mid) ret=cmp(ret,query(t[x].ls,l,mid,L,R));
        if(mid<R) ret=cmp(ret,query(t[x].rs,mid+1,r,L,R));
        return ret;
    }
    void ins(int l,int c,int d){
        int p=nd;nd=++cnt;len[nd]=l;
        for(;p&&ch[p][c]==0;p=f[p][0]) ch[p][c]=cnt;
        int q;
        if(!p){
            f[nd][0]=1;goto abc;
        }
        q=ch[p][c];
        if(len[q]==len[p]+1){
            f[nd][0]=q;goto abc;
        }
        len[++cnt]=len[p]+1;
        f[cnt][0]=f[q][0];f[q][0]=f[nd][0]=cnt;
        for(reg i=0;i<26;++i) ch[cnt][i]=ch[q][i];
        for(;p&&ch[p][c]==q;p=f[p][0]) ch[p][c]=cnt;
        abc:;
        upda(rt[nd],1,m,d,1);
    }
    void wrk(char *s){
        int lth=strlen(s+1);
        int now=1;
        int l=0;
        for(reg i=1;i<=lth;++i){
            int x=s[i]-'a';
        //    cout<<" wrk "<<i<<" "<<now<<" "<<l<<endl;
            if(ch[now][x]==0){
                while(now&&ch[now][x]==0) now=f[now][0];
                if(!now){
                    l=0;
                    pos[i]=1;
                    now=1;pi[i]=0;
                }
                else{
                    l=len[now]+1;
                    now=ch[now][x];
                    pi[i]=l;pos[i]=now;
                }
            }else{
        //        cout<<" ok "<<endl;
                ++l;
                now=ch[now][x];
                pi[i]=l;pos[i]=now;
            }
        }
    }
    struct edge{
        int nxt,to;
    }e[2*M];
    int hd[2*M],tot;
    void add(int x,int y){
        e[++tot].nxt=hd[x];
        e[tot].to=y;
        hd[x]=tot;
    }
    void dfs(int x){
        //cout<<" xx "<<x<<" fa "<<f[x][0]<<endl;
        //cout<<" rt[21] "<<rt[21]<<" "<<t[rt[21]].id<<" "<<t[rt[21]].mx<<endl;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            dfs(y);
            //cout<<" mergeing "<<rt[x]<<" "<<rt[y]<<endl;
        //    cout<<" before  rt[21] "<<rt[21]<<" "<<t[rt[21]].id<<" "<<t[rt[21]].mx<<endl;
            rt[x]=merge(rt[x],rt[y],1,m);
            //cout<<" after rt[21] "<<rt[21]<<" "<<t[rt[21]].id<<" "<<t[rt[21]].mx<<endl;
        }
    }
    void build(){//add_edge+dfs+merge+beizeng
        for(reg i=2;i<=cnt;++i) add(f[i][0],i);
        dfs(1);
        for(reg j=1;j<=19;++j){
            for(reg i=1;i<=cnt;++i){
                f[i][j]=f[f[i][j-1]][j-1];
            }
        }
    }
    pair<int,int>sol(int p,int l,int L,int R,int lp){
        //if(lp==53) cout<<" p "<<p<<" ll "<<l<<" : "<<pos[p]<<" "<<pi[pos[p]]<<" L R "<<L<<" "<<R<<" lp "<<lp<<endl;
        if(pi[p]<l) return make_pair(L,0);
        p=pos[p];
        for(reg j=19;j>=0;--j){
            if(len[f[p][j]]>=l) p=f[p][j];
        }
        //if(lp==53) cout<<" after jump "<<p<<" "<<len[p]<<" : "<<f[p][0]<<" "<<len[f[p][0]]<<" "<<rt[p]<<endl;
        pair<int,int>ret=query(rt[p],1,m,L,R);
        if(ret.first==0) ret.first=L;
        return ret;
    }
    void main(){
        scanf("%s",s+1);
        //num=1;
        //rt[1]=1;
        
        rd(m);
        init();
        for(reg i=1;i<=m;++i){
            int now=0;
            scanf("%s",a+1);
            now=strlen(a+1);
            nd=1;
            for(reg j=1;j<=now;++j){
                ins(j,a[j]-'a',i);
            }
            //cout<<" rt[2] "<<rt[2]<<" "<<t[rt[2]].id<<" "<<t[rt[2]].mx<<endl;
        }
        wrk(s);
        //int lll=strlen(s+1);
//        for(reg i=1;i<=lll;++i){
//            cout<<i<<" : "<<pos[i]<<endl;
//        }
        build();
        //cout<<" rt[2] "<<rt[2]<<" "<<t[rt[2]].id<<" "<<t[rt[2]].mx<<endl;
        
        int q;
        rd(q);
        int l,r,pl,pr;
        int o=0;
        while(q--){
            rd(l);rd(r);rd(pl);rd(pr);
            pair<int,int>ans=sol(pr,pr-pl+1,l,r,++o);
            printf("%d %d\n",ans.first,ans.second);
        }
    }
}sam;
int main(){
    sam.main();
    return 0;
}
}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/12/31 10:57:37
*/      

總結：

思路還是簡單自然的

要多串的子串比對，就廣義SAM

詢問和S子串有關，就先跑一下比對