#C240129A. The Phantom Menace
标签(Label)
- 欧拉回路
- 哈希表
网址(Website)
$\qquad$ Problem - J - Codeforces
题解(Solution)
$\qquad$ 首先,枚举差位 $d$,易证枚举次数只需要在 $0\le d\le m-1$ 中,若 $d$ 大于了 $m-1$ 则一定有另外一种排列使得差位 $d$ 小于 $m-1$ 。
$\qquad$ 对于 $d=0$ 的情况,直接先sort
排序,,排序之后判断字符是否相等即可,注意排序后字符的对应问题,还有就是不要打乱字符串的原始顺序,否则会影响到输出。
$\qquad$ 对于 $d\ne 0 $ 的情况,我们将每个字符分为前缀和后缀,其中 $A$ 串中的分为 $[0,d)$ 与 $[d,m)$ ,$B$ 串中的分为 $[0,m-d)$ 与 $[m-d,m)$。接着将其转换成哈希值。对于每一个长度为 $m$ 的字符串,我们将其看成一条从 前缀对应的点 连到 后缀对应的点 的边,可以发现,当这样建成的图构成欧拉回路时,当前的 $d$ 可以组成循环同构。
$\qquad$ 注意:不要想着用 $map$ 来代替哈希,会超时。在 $A$ 排列中的字符串 $ab$ 与在 $B$ 中的字符串 $ab$ 并不是同一个点,可以用类似二分图的编号方法来区分。
代码(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;
}