把所有串接在一起，用不同的分隔符分隔，

然后跑后缀数组。。

对于每个询问串暴力跑出height大于询问串长度的区间统计答案即可。。。。。。。。。。。。。。但是在洛谷上这种做法被卡掉了

面向数据加个优化水过。

1 #include
     
        2 #define R register  3 using namespace std;  4 const int N=50010,M=100010,T=500010;  5 int n,m,s,tot,len[M],head[M],qpos[T];  6 int ans[M],res[N];  7 int str[T],x[T<<1],y[T<<1],sa[T],rank[T],h[T],height[T],cnt[T],bel[T];  8 bool qvis[M];  9 inline int read(){ 10     int x=0,w=1;char c=0; 11     while(c<'0'||c>'9'){
   if(c=='-') w=-1;c=getchar();} 12     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); 13     return x*w; 14 } 15 inline void build(){ 16     for(R int i=1;i<=tot;i++) cnt[x[i]]++; 17     for(R int i=1;i<=s;i++) cnt[i]+=cnt[i-1]; 18     for(R int i=tot;i;i--) sa[cnt[x[i]]--]=i; 19     for(R int i=0;i<=s;i++) cnt[i]=0; 20     for(R int k=1;k<=tot;k<<=1){ 21         int num=0; 22         for(R int i=tot;i>tot-k;i--) y[++num]=i; 23         for(R int i=1;i<=tot;i++) if(sa[i]>k) y[++num]=sa[i]-k; 24         for(R int i=1;i<=tot;i++) cnt[x[i]]++; 25         for(R int i=1;i<=s;i++) cnt[i]+=cnt[i-1]; 26         for(R int i=tot;i;i--) sa[cnt[x[y[i]]]--]=y[i]; 27         for(R int i=0;i<=s;i++) cnt[i]=0; 28         swap(x,y); 29         x[sa[1]]=num=1; 30         for(int i=2;i<=tot;i++){ 31             if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) num++; 32             x[sa[i]]=num; 33         } 34         if(num>=tot) break; 35         s=num; 36     } 37     int t=0; 38     for(R int i=1;i<=tot;i++) rank[sa[i]]=i; 39     for(R int i=1;i<=tot;i++){ 40         if(t) t--; 41         while(rank[i]-1&&str[i+t]==str[sa[rank[i]-1]+t]) t++; 42         h[i]=t,height[rank[i]]=t; 43     } 44     return; 45 } 46 int vis[N],timer; 47 vector
      
       curq,curstu; 48 inline void que(int id){ 49     int totq=0,totstu=0,qh=len[id]; 50     timer++; 51     R int p=rank[head[id]]; 52     curq.push_back(id);totq++; 53     while(p>=1&&height[p]>=qh){ 54         p--; 55         if(qpos[p]&&len[qpos[p]]==qh){ 56             curq.push_back(qpos[p]); 57             totq++; 58         } 59         if(bel[sa[p]]&&vis[bel[sa[p]]]!=timer){ 60             vis[bel[sa[p]]]=timer,totstu++; 61             curstu.push_back(bel[sa[p]]); 62         } 63     } 64     p=rank[head[id]]+1; 65     while(p<=tot&&height[p]>=qh){ 66         if(qpos[p]&&len[qpos[p]]==qh){ 67             curq.push_back(qpos[p]); 68             totq++; 69         } 70         if(bel[sa[p]]&&vis[bel[sa[p]]]!=timer){ 71             vis[bel[sa[p]]]=timer,totstu++; 72             curstu.push_back(bel[sa[p]]); 73         } 74         p++; 75     } 76     for(R int i=0;i