题意：给n个字符串和q个询问，每个询问给两个数字x,y，问1.x是否为y的子序列，2.x是否为y的子串，是输出1，否则输出0，每个询问输出2个数字
题解：
对于子序列，朴素的做法，每次询问的复杂度为max(str[x],str[y])，题目好像有数据卡这个做法，反正会T，正解应该是建立一个序列自动机，首先将所有的字符串连续存起来，用数组来保存每个字符串的位置，然后dp[i][j]表示第i个字符的下一个字符的位置，询问的时候就能做到复杂度为min(str[x],str[y])。、
对于子串，可以用AC自动机来预处理，子串的询问有点特别，不是一般的在树上走，而是对每个节点进行寻找，然后用map来记录关系，不过在询问的时候也有个优化，不加这个优化一样会T，加了瞬间变成170+ms,具体看代码。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef pair<int,int>P; 5 6 const int N=1e5+7; 7 int t,n,m,L[N],R[N],loc[N],dp[N][26],Q[N][2],ans[N][2]; 8 char str[N]; 9 map<P,int>ok; 10 const int AC_N=N,tyn=26;//数量乘串长,类型数 11 struct AC_automation{ 12 int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot; 13 inline int getid(char x){return x-'a';} 14 void nw(){cnt[++tot]=0,fail[tot]=0;memset(tr[tot],0,sizeof(tr[tot]));} 15 void init(){tot=-1,fail[0]=-1,nw();} 16 void insert(int l,int r,int x=0){ 17 for(int i=l,w;i<=r;x=tr[x][w],loc[i]=x,i++) 18 if(!tr[x][w=getid(str[i])])nw(),tr[x][w]=tot; 19 cnt[x]++;//串尾标记 20 } 21 void build(int head=1,int tail=0){ 22 for(int i=0;i<tyn;i++)if(tr[0][i])Q[++tail]=tr[0][i]; 23 while(head<=tail)for(int x=Q[head++],i=0;i<tyn;i++) 24 if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q[++tail]=tr[x][i]; 25 else tr[x][i]=tr[fail[x]][i]; 26 } 27 void ask(int l,int r) 28 { 29 F(i,l,r)for(int p=loc[i];p;p=fail[p]) 30 if(cnt[p])ok[P(p,loc[r])]=1; 31 else if(fail[p]&&!cnt[fail[p]])fail[p]=fail[fail[p]];//决定是否T的优化 32 } 33 }AC; 34 35 void work1() 36 { 37 F(i,0,25)dp[R[n]+1][i]=N;//建立“子序列自动机” 38 for(int i=R[n];i>=1;i--)F(j,0,25) 39 if(str[i]==j+'a')dp[i][j]=i; 40 else dp[i][j]=dp[i+1][j]; 41 F(i,1,m) 42 { 43 int x=Q[i][0],y=Q[i][1]; 44 if(R[x]-L[x]>R[y]-L[y])ans[i][0]=0; 45 else 46 { 47 ans[i][0]=1; 48 for(int j=L[x],p=L[y];j<=R[x];j++,p++) 49 { 50 p=dp[p][str[j]-'a']; 51 if(p>R[y]){ans[i][0]=0;break;} 52 } 53 } 54 } 55 } 56 57 void work2() 58 { 59 AC.init(),ok.clear(); 60 F(i,1,n)AC.insert(L[i],R[i]); 61 AC.build(); 62 F(i,1,n)AC.ask(L[i],R[i]); 63 F(i,1,m)ans[i][1]=ok[P(loc[R[Q[i][0]]],loc[R[Q[i][1]]])]; 64 } 65 66 int main() 67 { 68 scanf("%d",&t); 69 while(t--) 70 { 71 scanf("%d%d",&n,&m); 72 int ed=1; 73 F(i,1,n) 74 { 75 scanf("%s",str+ed); 76 int len=strlen(str+ed); 77 L[i]=ed,R[i]=ed+len-1,ed=R[i]+1; 78 } 79 F(i,1,m)scanf("%d%d",&Q[i][0],&Q[i][1]); 80 work1(),work2(); 81 F(i,1,m)printf("%d%d",ans[i][0],ans[i][1]); 82 puts(""); 83 } 84 return 0; 85 }