思路： 将4个串每个串都反向这样得到新的四个串一共8个串，对于母串每个位置检测这个串能不能放进去，hs或者后缀数组都可以。然后dp[i][j] (0<i<len 0<=j<8)表示长度为i以第j个串结尾能不能到达，如果能 那么 就可以i+1位置利用原来处理出来的来转移。要注意开头结尾即可。
注意：以第i个串结尾 那么下个串 就不能用第i个串的反向串。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<time.h>
#include<string>
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,a,b) for(int i=a;i<=b;++i)
#define REP2(i,a,b) for(int i=a;i>=b;--i)
#define MP make_pair
#define LL long long
#define ULL unsigned long long
#define X first
#define Y second
#define MAXN 100050
using namespace std;
int pre[MAXN][];
bool bo[MAXN][];
bool dp[MAXN][];
bool ed[MAXN][];
ULL hs[][MAXN];
ULL p[MAXN];
int id[][MAXN];
char s[][MAXN];
int len[];
void makehs(int id){
hs[id][]=;
for(int i=;i<=len[id];++i)
hs[id][i]=hs[id][i-]*+s[id][i-]-'a'+;
}
ULL geths(int id,int l,int r){
l--;
return hs[id][r]-hs[id][l]*p[r-l];
}
int q[MAXN];
int tail;
void out(int cid,int l,int r)
{
for(int i=r;i>=l;--i)
q[tail++]=id[cid][i];
}
int main() {
p[]=;
for(int i=;i<MAXN;++i)p[i]=p[i-]*;
int tt,n,m;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d",&n,&m);
memset(bo,,sizeof(bo));
memset(dp,,sizeof(dp));
memset(ed,,sizeof(ed));
memset(pre,-,sizeof(pre));
int cid=;
for(int i=;i<;++i){
scanf(" %s",s[i*]);
len[i*]=len[i*+]=strlen(s[i*]);
for(int j=;j<len[i*];++j)
{
s[i*+][j]=s[i*][len[i*]-j-];
id[i*][j]=cid;
id[i*+][len[i*]-j-]=cid++;
}
makehs(i*);
makehs(i*+);
}
scanf(" %s",s[]);
len[]=strlen(s[]);
makehs();
//整串转移
for(int i=;i<m;++i){
for(int j=;j<;++j){
if(i+len[j]<=m){
ULL tmp1=geths(,i+,i+len[j]);
ULL tmp2=geths(j,,len[j]);
if(tmp1!=tmp2)continue;
bo[i][j]=true;
}
}
} //开头
for(int i=;i<m;++i){
for(int j=;j<;++j){
if(len[j]>i){
ULL tmp1=geths(,,i+);
ULL tmp2=geths(j,len[j]-i,len[j]);
if(tmp1!=tmp2)continue;
dp[i][j]=true;
}
}
} //结尾
for(int i=;i<m;++i){
for(int j=;j<;++j){
if(len[j]>len[]-i){
ULL tmp1=geths(,i+,len[]);
ULL tmp2=geths(j,,len[]-i);
if(tmp1!=tmp2)continue;
ed[i][j]=true;
}
}
} int pos=-,posx,flag=,fol;
//转移
for(int i=;i<m;++i){
for(int j=;j<;++j){
if(!dp[i][j])continue;
if(i==m-){
pos=i;
posx=j;
flag=;
break;
}
for(int k=;k<;++k){
if((j^k)==)continue;
if(!ed[i+][k])continue;
pos=i;
posx=j;
fol=k;
flag=;
break;
}
for(int k=;k<;++k){
if((j^k)==)continue;
if(!bo[i+][k])continue;
dp[i+len[k]][k]=true;
pre[i+len[k]][k]=j;
}
}
if(flag)break;
}
if(flag==)
{
puts("No solution!");
continue;
}
tail=;
if(pos!=m-){
out(fol,,m-pos-);
}
while(posx!=-){
if(len[posx]>pos+)out(posx,len[posx]-pos-,len[posx]-);
else out(posx,,len[posx]-);
int tmpx=posx;
posx=pre[pos][posx];
pos=pos-len[tmpx];
}
for(int i=tail-;i>;--i)printf("%d ",q[i]);
printf("%d\n",q[]);
}
return ;
}
/*
1
3 3
abc
abc
abc
abc
baa*/
