The 2023 CCPC Guilin J. The Phantom Menace

好劲的字符串题，然而实际上和字符串没啥关系

比赛的时候全队应该就只有我没读过题面，感觉如果让我看到这个重排+循环同构第一反应肯定是枚举偏移量+Hash比较前后缀，因为我字符串算法高级的不会只会一个Hash，说不定能搞出点想法

但今天补的时候发现写起来细节还是挺多的，尤其是有向图的欧拉回路和无向图版本不太一样，去网上重新找了个写法才过

回到题目，循环同构的解决思路一般就是枚举一个偏移量\(x\)，之后我们发现问题转化为：

• 第一个集合中的串长度为\(x\)的前缀和第二个串中长度为\(x\)的后缀匹配
• 第二个集合中长度为\(n-x\)的前缀和第一个集合中长度为\(n-x\)的后缀匹配

一个很直观的想法就是把每个字符串看成点，然后把分割后有相同部分的关系看成边，但这样有个问题就是可能会出现边数爆炸的情况

因此不妨换个角度思考，把对应长度的前后缀看成点，然后将字符串看作边，这样图中的边数就是\(O(n)\)级别的，同时相同部分由于会映射到同一个点上，也就变相实现了匹配的功能

再手玩一下就会发现此时题目转化为在得到的图上找一个欧拉回路，然后直接上板子即可

总复杂度\(O(n\times m)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
int t,n,m,deg[N],idx; char s[N]; vector <pi> v[N];
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	inline LL get_val(void)
	{
		return ((1LL*x)<<31LL)|(1LL*y);
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}pw[N]; vector <Hasher> h[N]; vector <int> path; int used[N];
const Hasher seed=Hasher(31,131);
inline void init(CI n)
{
	pw[0]=Hasher(1,1); for (RI i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
}
inline Hasher get_hsh(CI id,CI l,CI r)
{
	return h[id][r]-h[id][l-1]*pw[r-l+1];
}
inline void DFS(CI now)
{
	while (!v[now].empty())
	{
		int to=v[now].back().fi,id=v[now].back().se; v[now].pop_back();
		if (used[id]) continue; DFS(to); used[id]=1; path.push_back(id);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(1e6);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=2*n;++i)
		{
			h[i].resize(m+1); h[i][0]=Hasher(); scanf("%s",s+1);
			for (j=1;j<=m;++j) h[i][j]=h[i][j-1]*seed+Hasher(s[j],s[j]);
		}
		bool sign=0; for (i=0;i<m;++i) //shift
		{
			for (j=1;j<=idx;++j) deg[j]=0,v[j].clear(); idx=0;
			map <LL,int> rst[2]; int st;
			auto get_id=[&](CI tp,const LL& val)
			{
				if (!rst[tp].count(val)) rst[tp][val]=++idx; return rst[tp][val];
			};
			for (j=1;j<=n;++j)
			{
				int x=get_id(0,get_hsh(j,1,i).get_val()),y=get_id(1,get_hsh(j,i+1,m).get_val());
				st=x; v[x].push_back(pi(y,j)); ++deg[x]; --deg[y];
			}
			for (j=n+1;j<=2*n;++j)
			{
				int x=get_id(1,get_hsh(j,1,m-i).get_val()),y=get_id(0,get_hsh(j,m-i+1,m).get_val());
				v[x].push_back(pi(y,j)); ++deg[x]; --deg[y];
			}
			bool flag=1; for (j=1;j<=idx;++j) if (deg[j]) { flag=0; break; }
			if (!flag) continue; path.clear(); for (j=1;j<=2*n;++j) used[j]=0;
			/*for (j=1;j<=idx;++j)
			{
				printf("%d -> ",j);
				for (auto [x,y]:v[j]) printf("(%d,%d) ",x,y); putchar('\n');
			}*/
			DFS(st); for (j=1;j<=2*n;++j) if (!used[j]) { flag=0; break; }
			if (!flag) continue; reverse(path.begin(),path.end());
			vector <int> pa,pb; for (auto x:path)
			if (x<=n) pa.push_back(x); else pb.push_back(x-n);
			sign=1; for (auto x:pa) printf("%d ",x); putchar('\n');
			for (auto x:pb) printf("%d ",x); putchar('\n'); break;
		}
		if (!sign) puts("-1");
	}
	return 0;
}