题目描述

给你一个串S以及一个字符串数组T[1..m]，q次询问，每次问S的子串S[pl​..pr​]在T[l..r]中的哪个串里的出现次数最多，并输出出现次数。

如有多解输出最靠前的那一个。

题解

算是道字符串比较套路的题吧。

对模式串建SAM，对所有模式串的所有前缀维护right集合。

然后对于每个询问，倍增找到关键点，查子树众数。

坑：在最匹配串做匹配的时候，要记录匹配长度，如果匹配长度不够询问长度，直接判无解。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #define N 1000009using namespace std;typedef long long ll;int ch[N][26],tott,tr[N*32],id[N*32],ls[N*32],rs[N*32],ans1,ans2,fa[N],mat[N];int cnt,last,l[N],tot,head[N],n,p[21][N],deep[N],T[N],tag[N];char s[N],s1[N];inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}void upd(int &cnt,int l,int r,int x){    if(!cnt)cnt=++tott;    if(l==r){tr[cnt]++;id[cnt]=l;return;}    int mid=(l+r)>>1;    if(mid>=x)upd(ls[cnt],l,mid,x);    else upd(rs[cnt],mid+1,r,x);    tr[cnt]=max(tr[ls[cnt]],tr[rs[cnt]]);    id[cnt]=tr[ls[cnt]]>=tr[rs[cnt]]?id[ls[cnt]]:id[rs[cnt]];}int merge(int x,int y,int l,int r){    if(!x||!y)return x^y;    int p=++tott;    if(l==r){tr[p]=tr[x]+tr[y];id[p]=l;return p;}    int mid=(l+r)>>1;    ls[p]=merge(ls[x],ls[y],l,mid);rs[p]=merge(rs[x],rs[y],mid+1,r);    tr[p]=max(tr[ls[p]],tr[rs[p]]);    id[p]=tr[ls[p]]>=tr[rs[p]]?id[ls[p]]:id[rs[p]];    return p;}void query(int cnt,int l,int r,int L,int R){    if(!cnt)return;    if(l>=L&&r<=R){        if(tr[cnt]>ans1){            ans1=tr[cnt];            ans2=id[cnt];        }        return;    }     int mid=(l+r)>>1;    if(mid>=L)query(ls[cnt],l,mid,L,R);    if(mid
         
          =0;--i)if(l[p[i][x]]>=r1-l1+1)x=p[i][x];                ans1=0;ans2=l2;;        query(T[x],1,n,l2,r2);        printf("%d %d\n",ans2,ans1);    }    return 0;}