题面

传送门

思路

首先，看到这个区间询问和多串的结构，应该能想到一些trie-based的算法，以及处理区间询问的数据结构

考虑到本题实际上问的是一个子串匹配问题，因此我们首先考虑$AC$自动机能不能处理——

然后我们发现，本题询问的不只是能否匹配，还要求给出匹配次数

这就引导我们使用广义后缀自动机

我们首先对于给定的字符串集合建立广义后缀自动机，备用【这个词怎么感觉一副做菜教程的样子hhhhh】

考虑到给出的询问串都是同一个字符串的子串，而我们的询问中的匹配母串（也就是被匹配的串）已经躺在$SAM$里面了

那么我们把询问串放到$SAM$里面去跑一趟，跑出来每个前缀在$SAM$中的最长匹配后缀的位置（位置指SAM中的节点）

这样，对于询问要求匹配模板串是$s[l...r]$的询问，我们只要从$s[r]$对应的位置再沿着$fail$树跳，就可以一步一步去掉$s[1...r]$这个串最前面的字符，得到$s[l...r]$

那么我们只需要知道我们跳到的这个节点都是哪些$t_i$的子串、以及在它们中出现的次数就好了。

这个过程可以通过建立$fail$树，并在上面使用线段树合并做到

线段树以$t$串的下标为下标，维护每个串在每个节点的出现次数

对于之前沿着$fail$树跳节点找询问的$s[l...r]$对应的节点，我们可以使用树上倍增预处理好各个询问，最后和线段树合并一起在同一个$dfs$里面解决

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<queue>
#include<vector>
#define ll long long
#define log DDEP_DARK_FANTASY
using namespace std;
inline int read(){
    int re=0,flag=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
int n,m,q;char s[1000010],tt[1000010];
vector<int>q1[500010],q2[500010];
int sl[500010],sr[500010],ql[500010],qr[500010],st[500010][20],log[500010];
namespace sam{//广义SAM，不维护东西，作用其实只有建立fail树，线段树的初始化在main里面
    int ch[400010][26],fa[400010],val[400010],root,cnt,last;
    void init(){root=cnt=1;val[1]=0;}
    inline int newnode(int w){val[++cnt]=w;return cnt;}
    void insert(int c){
        int p=last,np=newnode(val[p]+1);
        for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if(!p) fa[np]=root;
        else{
            int q=ch[p][c];
            if(val[q]==val[p]+1) fa[np]=q;
            else{
                int nq=newnode(val[p]+1);
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q];
                fa[q]=fa[np]=nq;
                for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
        last=np;
    }
}
namespace seg{//线段树（以及合并）
    struct ele{
        int pos,num;
        ele(int aaa=1e8,int bbb=0){num=bbb;pos=aaa;}
        inline bool operator <(const ele &b)const{
            return (num==b.num)?pos>b.pos:num<b.num;
        }
        friend inline ele max(ele a,ele b){return (a<b)?b:a;}
    }seg[800010],ans[800010];
    int ch[800010][2],cnt;
    void insert(int &cur,int l,int r,int pos){
        if(!cur) cur=++cnt;
//      cout<<"insert "<<cur<<' '<<l<<' '<<r<<' '<<pos<<'\n';
        if(l==r){seg[cur].num++;seg[cur].pos=pos;return;}
        int mid=(l+r)>>1;
        if(mid>=pos) insert(ch[cur][0],l,mid,pos);
        else insert(ch[cur][1],mid+1,r,pos);
        seg[cur]=max(seg[ch[cur][0]],seg[ch[cur][1]]);
    }
    int merge(int x,int y){
        if(!x||!y) return x^y;
        if(!ch[x][0]&&!ch[x][1]){seg[x].num+=seg[y].num;return x;}
        ch[x][0]=merge(ch[x][0],ch[y][0]);
        ch[x][1]=merge(ch[x][1],ch[y][1]);
        seg[x]=max(seg[ch[x][0]],seg[ch[x][1]]);
        return x;
    }
    ele query(int cur,int l,int r,int ql,int qr){
//      cout<<"seg query "<<cur<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<'\n';
        if(l>=ql&&r<=qr) return seg[cur];
        int mid=(l+r)>>1;ele re;
        if(mid>=ql) re=max(re,query(ch[cur][0],l,mid,ql,qr));
        if(mid<qr) re=max(re,query(ch[cur][1],mid+1,r,ql,qr));
        return re;
    }
}
namespace g{//fail树
    int first[400010],cnte=-1,root[400010];
    void init(){memset(first,-1,sizeof(first));}
    struct edge{
        int to,next;
    }a[800010];
    inline void add(int u,int v){
        a[++cnte]=(edge){v,first[u]};first[u]=cnte;
        a[++cnte]=(edge){u,first[v]};first[v]=cnte;
    }
    void dfs(int u,int f){
        int i,v;
//      cout<<"dfs "<<u<<' '<<f<<' '<<root[u]<<'\n';
        for(i=first[u];~i;i=a[i].next){
            v=a[i].to;if(v==f) continue;
            dfs(v,u);root[u]=seg::merge(root[u],root[v]);
        }
        assert(root[u]);
        for(i=0;i<q2[u].size();i++){
            v=q2[u][i];
            seg::ans[v]=seg::query(root[u],1,m,ql[v],qr[v]);
//          cout<<" query "<<v<<' '<<seg::ans[v].pos<<' '<<seg::ans[v].num<<'\n';
        }
    }
}
int main(){
    g::init();sam::init();int i,j,k,len,u,dep,v,cur;
    scanf("%s",s);n=strlen(s);
    m=read();
    for(i=1;i<=m;i++){
        scanf("%s",tt);len=strlen(tt);
        sam::last=1;
        for(j=0;j<len;j++){//建立广义SAM
            sam::insert(tt[j]-'a');
//          cout<<"main inserted char "<<tt[j]<<", get last "<<sam::last<<'\n';
            seg::insert(g::root[sam::last],1,m,i);//直接往节点对应的线段树里面插入
        }
    }
    q=read();
    for(i=1;i<=q;i++){
        ql[i]=read();qr[i]=read();sl[i]=read()-1;sr[i]=read()-1;
        q1[sr[i]].push_back(i);
    }
    log[1]=0;
    for(i=2;i<=sam::cnt;i++){//建立fail树
        g::add(sam::fa[i],i);
        st[i][0]=sam::fa[i];
        log[i]=log[i>>1]+1;
    }
    for(j=1;j<=19;j++){
        for(i=1;i<=sam::cnt;i++){//预处理倍增
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
    for(u=1,dep=0,i=0;i<n;i++){//预处理询问
        while(u&&!sam::ch[u][s[i]-'a']) u=sam::fa[u],dep=sam::val[u];
        if(!u) u=1,dep=0;
        u=sam::ch[u][s[i]-'a'];dep++;
        for(j=0;j<q1[i].size();j++){
            v=q1[i][j];cur=u;
            if(dep<sr[v]-sl[v]+1) continue;
                        //这里需要注意，有可能出现s[l...r]根本没有在SAM中出现过的情况，需要排除
            for(k=19;k>=0;k--) if(sam::val[st[cur][k]]>=sr[v]-sl[v]+1) cur=st[cur][k];
            q2[cur].push_back(v);
        }
    }
    g::dfs(1,0);
    for(i=1;i<=q;i++){
        if(seg::ans[i].num==0) printf("%d 0\n",ql[i]);
        else printf("%d %d\n",seg::ans[i].pos,seg::ans[i].num);
    }
}

[CF666E] Forensic Examination [广义后缀自动机+线段树合并]

原文：https://www.cnblogs.com/dedicatus545/p/10352309.html