题意：

给你N个串对，M个询问串，对每个询问串求是多少串对的子串（在串对的某一个中作为子串），以及每个串对最终是包含了多少询问串

 

方法众多。。

可谓字符串家族八仙过海各显神通。

复杂度不尽相同，O(nlogn),O(nsqrt(n)),O(玄学)（也就是暴力）

（数据比较水，所以一些暴力就过去了）

做法基本都是离线。

 

法一：AC自动机+暴力

对询问串建AC自动机，把主串往上跑。

匹配到了一个节点，就暴力跳fail，把沿途的点如果是询问串的结尾，ans++，并打上标记，防止重复计数。

一串1111111，随便卡。

法二：AC自动机+hash

询问串或者主串可能有相同的，，，hash一下，减少理论复杂度。。。

还是随便卡。

法三：AC自动机+fail树虚树

这个是正解O(nlogn)。

但是不会虚树，咕咕咕。

法四：后缀数组+hash

AC自动机比较辣鸡，后缀家族表示不服。

一个后缀的和询问串的lcp是询问串的长度的话，那么这个询问串就是子串。

考虑一个询问会被哪些后缀包含，我们把所有的询问串和子串用分隔符隔开，然后跑SA，HEIGHT

对于每个询问串的开头位置，往左往右二分出所有出现的位置。

这个区间[l,r]就是这个询问串的所有出现位置~！

（

luogu题解第一篇dalao说，可以不用二分，线性处理出l,r的位置。

然后我写了单调队列，，，，然鹅显然这个区间端点并没有单调性。。。然后WA了半天。。。。

不知是这个dalao口胡错了，还是我太菜了？

）

怎么统计答案？

由于区间长度期(shu)望(ju)不(tai)大(shui)，可以暴力扫一遍这个区间，然后轻松统计答案。

一串111111，应该还是能卡。

法五：后缀数组+莫队

莫队教导我们：干嘛要直接暴力？

处理出询问区间之后，莫队可以轻松统计第一问，

第二问的话：差分。每新加入一个颜色，就把这个颜色的答案加上剩余询问的次数，删除这个颜色的时候，就把剩余次数减掉。这样，处理所有包含这个颜色的询问的时候，这些询问一定贡献到了这个颜色里。

O(nsqrt(n))

法六：后缀数组+树状数组

莫队归根到底，还是暴力啊。。。。

再看一看第一问是什么：统计区间颜色的数量？哦，，

树状数组来也。

第二问呢？反过来，把询问当做树状数组中加入的点值。

到L的时候，bit(L)++,到R的时候，bit(L)--，到i的时候，ans+=query(i)-query(pre[i])

类似扫描线。

本质上还是对于每个颜色第一次被区间包含的时候，把这个区间的贡献加上。为什么这里要把bit(L)--？为了消除区间两端在中间的情况。

 

那为什么不把bit(R)--？这样前面的相同部分并不能减去

 

 反而加上了-1

我写的就是这个方法：

注意：

1.还是二分吧。。

2.注意我们是在SA数组上操作，pos记录的是原串的所属，所以，在SA上循环的时候，查询这个后缀的所属，用pos[sa[i]]

#include
      
       #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;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=4e5+5;const int C=1e4+2;int x[N],y[N],c[N],sa[N],hei[N],rk[N];int n,m;int s[N+233];void SA(int n){    int m=C+2;    for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];    for(reg i=1;i<=m;++i) c[i]+=c[i-1];    for(reg i=1;i<=n;++i) sa[c[x[i]]--]=i;    for(reg k=1;k<=n;k<<=1){        int num=0;        for(reg i=n-k+1;i<=n;++i) y[++num]=i;        for(reg i=1;i<=n;++i){            if(sa[i]-k>=1) y[++num]=sa[i]-k;        }        for(reg i=1;i<=m;++i) c[i]=0;        for(reg i=1;i<=n;++i) ++c[x[i]];        for(reg i=1;i<=m;++i) c[i]+=c[i-1];        for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;        swap(x,y);        num=1;        x[sa[1]]=1;        for(reg i=2;i<=n;++i){            x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i-1]+k]==y[sa[i]+k])?num:++num);        }        if(num==n) break;        m=num;    } }void HEI(int n){    for(reg i=1;i<=n;++i) rk[sa[i]]=i;    int k=0;    for(reg i=1;i<=n;++i){        if(k)--k;        if(rk[i]==1) continue;        int j=sa[rk[i]-1];        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;        hei[rk[i]]=k;    }}int pos[N],pre[N],las[N],id[N];int nxt[N];struct question{    int L,R,id,ans;    bool friend operator <(question a,question b){        return a.L
       
        b.c;    }}po[2*N];int cnt;int chang[N];int f[N][20];int lg[N];int tot;int query(int x,int y){    if(x==y) return tot-x+1;    if(x>y) swap(x,y);    ++x;    int len=lg[y-x+1];//    cout<<" rmq "<
        
         <<" "<
         
          <<" "<
          
           <
           
            <
            
             >(lg[i-1]+1))?lg[i-1]+1:lg[i-1]; } for(reg j=1;j<=18;++j){ for(reg i=1;i+(1<
             
              <=n;++i){ f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); //cout<<" i j "<
              <<" "<
               
                <<" : "<
                
                 <
                 
                  0){ int tmp=i; int l=1,r=i-1; que[id[sa[i]]].id=id[sa[i]]; while(l<=r){ int mid=(l+r)>>1; if(query(mid,i)>=chang[id[sa[i]]]) tmp=mid,r=mid-1; else l=mid+1; } que[id[sa[i]]].L=tmp; l=i+1,r=n; tmp=i; while(l<=r){ int mid=(l+r)>>1; if(query(i,mid)>=chang[id[sa[i]]]) tmp=mid,l=mid+1; else r=mid-1; } que[id[sa[i]]].R=tmp; } }}int ans1[N];int ans2[N];struct arraytree{ int f[N]; void add(int x,int c){ for(;x<=tot;x+=x&(-x)) f[x]+=c; } int query(int x){ int ret=0; for(;x;x-=x&(-x)) ret+=f[x]; return ret; }}t;int main(){ rd(n);rd(m); int len,x; tot=0; for(reg i=1;i<=n;++i){ rd(len); for(reg j=1;j<=len;++j){ rd(x); s[++tot]=x; id[tot]=0; pos[tot]=i; } s[++tot]=C;//warning!!! pos[tot]=-1;//warning!! -1 rd(len); for(reg j=1;j<=len;++j){ rd(x); s[++tot]=x; id[tot]=0; pos[tot]=i; } s[++tot]=C; pos[tot]=-1; } for(reg i=1;i<=m;++i){ rd(len); chang[i]=len; for(reg j=1;j<=len;++j){ rd(x); s[++tot]=x; pos[tot]=0; if(j==1) id[tot]=i; } s[++tot]=C; pos[tot]=-1; } SA(tot); HEI(tot); prewrk(tot); // cout<<" after "<
                  
                   0){ pre[i]=las[pos[sa[i]]]; las[pos[sa[i]]]=i; } } memset(las,0,sizeof las); for(reg i=tot;i>=1;--i){ if(pos[sa[i]]>0){ if(las[pos[sa[i]]])nxt[i]=las[pos[sa[i]]]; else nxt[i]=tot+1; las[pos[sa[i]]]=i; } } int now=1; for(reg i=1;i<=n;++i){ if(las[i]){ //cout<
                   <<" add fir "<
                    
                     <
                     
                      <
                      
                       <<" : "<
                       
                        <<" "<
                        
                         <<" "<
                         
                          <<" "<
                          
                           <
                           
                            0){ ans2[pos[sa[i]]]+=t.query(i)-t.query(pre[i]); } while(po[now].p==i&&now<=cnt){ t.add(po[now].L,po[now].c); ++now; } } for(reg i=1;i<=m;++i){ printf("%d\n",ans1[i]); } for(reg i=1;i<=n;++i){ printf("%d ",ans2[i]); } return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle* Date: 2018/12/23 11:39:01*/
                           
                          
                         
                        
                       
                      
                     
                    
                  
                 
                
               
             
            
           
          
         
        
       
      

 

法七：后缀数组+主席树+树状数组

emmm。。。

第一问也可以用主席树做。。。（虽然已经离线了，就完全没有必要了）

法八：后缀自动机+暴力

SAM大吼一声，怎么能少了俺？！？！

对所有的姓、名建广义SAM

可以对每个串的每个位置暴力跳parent树，把每个right集合的位置实际在多少个串上出现，叫做sz，记录下来。

询问的话，匹配一遍，如果中途没有失配，最后的匹配到节点的sz即为答案。

然后在这个点上打上tag++

最后，把所有的姓名串的每个位置再跑一遍，tag的总和就是被点名次数。当然，要在途中留下自己的标记，以防重复统计。

还是暴力。

一串111111应该还是可以卡掉？因为parent树退化成了一条链。

但是值得一提的是，这个算法总算是在线的！

法九：后缀自动机+莫队

思路来自：ywy_c_asm

莫队支持区间，那后缀自动机哪里有区间？

 

先把每个询问串在后缀自动机上跑一下，（失配直接puts0，然后滚蛋）

最后到了某个节点p，那么根据parent树的意义，p的子树中的所有点代表的位置都包含这个询问串！

于是，我们用莫队来搞dfn序！（具体所属情况，叶子就记录了。）

然后的方法大家就已经很熟悉了。（当然也可以用主席树或者树状数组做。）

 

---

 

upda：2019.3.8:

法十：后缀自动机+线段树合并

在线+O(nlogn)的算法

建出广义SAM，然后线段树合并，

跑询问串时候，查询线段树的sz就是第一问答案。然后打上tag标记

最后再来一次线段树合并。

到每个点时候把tag整个加到线段树上去。

到了root，dfs一遍线段树即可。