本文共 1594 字，大约阅读时间需要 5 分钟。
思路： 将4个串每个串都反向这样得到新的四个串一共8个串，对于母串每个位置检测这个串能不能放进去，hs或者后缀数组都可以。然后dp[i][j] (0<i<len 0<=j<8)表示长度为i以第j个串结尾能不能到达，如果能 那么 就可以i+1位置利用原来处理出来的来转移。要注意开头结尾即可。
注意：以第i个串结尾 那么下个串 就不能用第i个串的反向串。
#include #include #include #include #include #include #include #include #include #include #include #define REP(i,n) for(int i=0;i =b;--i)#define MP make_pair#define LL long long#define ULL unsigned long long#define X first#define Y second#define MAXN 100050using namespace std;int pre[MAXN][8];bool bo[MAXN][8];bool dp[MAXN][8];bool ed[MAXN][8];ULL hs[9][MAXN];ULL p[MAXN];int id[8][MAXN];char s[9][MAXN];int len[9];void makehs(int id){ hs[id][0]=1; for(int i=1;i<=len[id];++i) hs[id][i]=hs[id][i-1]*31+s[id][i-1]-'a'+1;}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[0]=1; for(int i=1;i i){ ULL tmp1=geths(8,1,i+1); ULL tmp2=geths(j,len[j]-i,len[j]); if(tmp1!=tmp2)continue; dp[i][j]=true; } } } //结尾 for(int i=0;i len[8]-i){ ULL tmp1=geths(8,i+1,len[8]); ULL tmp2=geths(j,1,len[8]-i); if(tmp1!=tmp2)continue; ed[i][j]=true; } } } int pos=-1,posx,flag=0,fol; //转移 for(int i=0;i pos+1)out(posx,len[posx]-pos-1,len[posx]-1); else out(posx,0,len[posx]-1); int tmpx=posx; posx=pre[pos][posx]; pos=pos-len[tmpx]; } for(int i=tail-1;i>0;--i)printf("%d ",q[i]); printf("%d\n",q[0]); } return 0;}/*13 3abcabcabcabcbaa*/
转载于:https://www.cnblogs.com/L-Ecry/p/3961131.html