题目链接:
题意:给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 #include2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef pair 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 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 =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 else46 { 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 }