#C240129A. The Phantom Menace

前言（Front talk)

To be honest, I was totallyn beaten by this problem.

网址（Website）

Problem - J - Codeforces

题解（Solution）

首先，枚举差位，易证枚举次数只需要在中，若大于了则一定有另外一种排列使得差位小于。

对于的情况，直接先sort排序，，排序之后判断字符是否相等即可，注意排序后字符的对应问题，还有就是不要打乱字符串的原始顺序，否则会影响到输出。

对于的情况，我们将每个字符分为前缀和后缀，其中串中的分为与，串中的分为与。接着将其转换成哈希值。对于每一个长度为的字符串，我们将其看成一条从 前缀对应的点 连到 后缀对应的点 的边，可以发现，当这样建成的图构成欧拉回路时，当前的可以组成循环同构。

注意：不要想着用来代替哈希，会超时。在排列中的字符串与在中的字符串并不是同一个点，可以用类似二分图的编号方法来区分。

代码（Code）

#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define Rof(i,l,r) for(register int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 1012345;
const int mod2 = 998244353; 
const int mod1 = 1e9+9;
const int bas = 129;

struct Hash{//双重hash
	vector<int> fac1,fac2,val1,val2;
	void Init(string s,int m){
		fac1.resize(m+5),fac2.resize(m+5);
		val1.resize(m+5),val2.resize(m+5);
		fac1[0]=fac2[0]=1,val2[0]=val2[0]=0;
		For(i,1,m) fac1[i]=fac1[i-1]*bas%mod1,fac2[i]=fac2[i-1]*bas%mod2;
		For(i,1,m) val1[i]=(val1[i-1]*bas+s[i-1])%mod1;
		For(i,1,m) val2[i]=(val2[i-1]*bas+s[i-1])%mod2;
	}
	inline int ask(int l,int r){
		int v1=((val1[r]-val1[l-1]*fac1[r-l+1])%mod1+mod1)%mod1;
		int v2=((val2[r]-val2[l-1]*fac2[r-l+1])%mod2+mod2)%mod2;
		return v1*2000000000ll+v2;
	}
}ha[N],hb[N];

string a[N],b[N];
int n,m;

vector<int> g,g1,g2;
vector<P> ft[N];
void dfs_road(int x,int id){//只要访问完所有的边，一定会构成欧拉回路
	while(ft[x].size()){
		auto p=ft[x].back();
		ft[x].pop_back();
		dfs_road(p.first,p.second);
	}if(id) g.emplace_back(id);
}

int inn[N],out[N];
int t1,t2;
inline bool check(){//欧拉回路的判断
	For(i,1,t1)   if(inn[i]!=out[i]) return false;
	For(i,n+1,t2) if(inn[i]!=out[i]) return false;
	dfs_road(1,0);if(g.size()!=2*n)  return false;
	return true;
}

//unordered_map<string,int> mp1,mp2;
unordered_map<int,int> mp1,mp2;

int ll[N],rr[N];
inline bool cmp1(int x,int y){return a[x]<a[y];}
inline bool cmp2(int x,int y){return b[x]<b[y];}
void Solve(){
	{//字符偏移量为 0 时
		For(i,1,n) ll[i]=i,rr[i]=i;
		sort(ll+1,ll+n+1,cmp1),
		sort(rr+1,rr+n+1,cmp2);
		bool flag=true;
		For(i,1,n) if(a[ll[i]]!=b[rr[i]]){flag=false;break;}
		if(flag){
			For(i,1,n) cout<<ll[i]<<' ';cout<<'\n';
			For(i,1,n) cout<<rr[i]<<' ';cout<<'\n';
			return; 
		}
	}
	
	For(d,1,m-1){
		For(i,1,n*2) ft[i].clear(),inn[i]=out[i]=0;
		mp1.clear(),mp2.clear(),
		g.clear(),g1.clear(),g2.clear();
		t1=0,t2=n;
		
		For(i,1,n){
			int sx(ha[i].ask(1,d)),sy(ha[i].ask(d+1,m));
//			string sx(a[i],0,d),sy(a[i],d,m);
			if(!mp1.count(sx)) mp1[sx]=++t1;
			if(!mp2.count(sy)) mp2[sy]=++t2;
			int x=mp1[sx],y=mp2[sy];
			ft[x].emplace_back(y,i);
//			cerr<<"A:"<<sx<<"->"<<sy<<"  "<<x<<"->"<<y<<'\n'; 
			out[x]++,inn[y]++;
		}
		
		bool flag=false;
		For(i,1,n){
			int sx(hb[i].ask(1,m-d)),sy(hb[i].ask(m-d+1,m));
//			string sx(b[i],0,m-d),sy(b[i],m-d,m);
			if(!mp2.count(sx)){flag=true;break;}
			if(!mp1.count(sy)){flag=true;break;}
			int x=mp2[sx],y=mp1[sy];
			ft[x].emplace_back(y,i+n);
//			cerr<<"B:"<<sx<<"->"<<sy<<"  "<<x<<"->"<<y<<'\n'; 
			out[x]++,inn[y]++;
		}if(flag || !check()) continue;
		while(g.size()){
			if(g.back()<=n) g1.emplace_back(g.back());
			else g2.emplace_back(g.back()-n);
			g.pop_back();
		}
		for(auto x:g1) cout<<x<<' ';cout<<'\n';
		for(auto x:g2) cout<<x<<' ';cout<<'\n';
		return;
	}return cout<<"-1\n",void();
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=input(),Tim=clock();
	while(T--){
		cin>>n>>m;
		For(i,1,n) cin>>a[i],ha[i].Init(a[i],m);
		For(i,1,n) cin>>b[i],hb[i].Init(b[i],m); 
		Solve();
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}