思路
后缀数组+博弈论的好题,首先对两个串都建出SAM,然后题目的要求实际上就是在SAM的trans上转移即可
DAG的博弈是经典问题,然后dfs求出SG函数,两个游戏的组合就是把SG函数异或起来,异或是0就是先手必败,不是0就是先手必胜
然后要求先手必胜,所以就是求异或不为0
接下来递推的求出第k大的串即可,类似于树上的第k大的思路
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MAXN = 100100*2;
struct SAM{
int trans[MAXN][26],suflink[MAXN],maxlen[MAXN],sg[MAXN],cnt;
long long cnt_sg[MAXN][28];
int new_state(int _maxlen,int *_trans,int _suflink){
++cnt;
maxlen[cnt]=_maxlen;
if(_trans)
for(int i=0;i<26;i++)
trans[cnt][i]=_trans[i];
suflink[cnt]=_suflink;
return cnt;
}
int add_len(int u,int c){
int z=new_state(maxlen[u]+1,NULL,0);
while(u&&(!trans[u][c])){
trans[u][c]=z;
u=suflink[u];
}
if(!u){
suflink[z]=1;
return z;
}
int v=trans[u][c];
if(maxlen[v]==maxlen[u]+1){
suflink[z]=v;
return z;
}
int y=new_state(maxlen[u]+1,trans[v],suflink[v]);
suflink[z]=suflink[v]=y;
while(u&&trans[u][c]==v){
trans[u][c]=y;
u=suflink[u];
}
return z;
}
int cal_sg(int u){
if(sg[u]!=-1)
return sg[u];
bool mid[30]={0};
for(int i=0;i<26;i++){
if(!trans[u][i])
continue;
int t=cal_sg(trans[u][i]);
mid[t]=true;
for(int j=0;j<27;j++)
cnt_sg[u][j]+=cnt_sg[trans[u][i]][j];
}
for(int i=0;i<30;i++)
if(!mid[i]){
sg[u]=i;
break;
}
cnt_sg[u][sg[u]]++;
for(int i=0;i<27;i++)
cnt_sg[u][27]+=cnt_sg[u][i];
return sg[u];
}
void init(char *s,int len){
int pre=1;
cnt=1;
for(int i=1;i<=len;i++)
pre=add_len(pre,s[i]-'a');
memset(sg,-1,sizeof(sg));
cal_sg(1);
}
}A,B;
int lena,lenb,mida;
long long k;
char sa[MAXN],sb[MAXN],ax[MAXN],bx[MAXN];
long long calc_mid(int Ax,int Bx){
long long ans=0;
for(int i=0;i<27;i++)
ans+=A.cnt_sg[Ax][i]*(B.cnt_sg[Bx][27]-B.cnt_sg[Bx][i]);
return ans;
}
int dfsA(int pos,int x){
int mid1=B.cnt_sg[1][27]-B.cnt_sg[1][A.sg[x]];
if(mid1>=k)
return x;
else
k-=mid1;
for(int i=0;i<26;i++){
if(!A.trans[x][i])
continue;
int mid2=calc_mid(A.trans[x][i],1);
if(mid2<k)
k-=mid2;
else{
ax[pos]='a'+i;
return dfsA(pos+1,A.trans[x][i]);
}
}
return -1;
}
int dfsB(int pos,int x){
k-=B.sg[x]!=A.sg[mida];
if(k==0)
return x;
for(int i=0;i<26;i++){
if(!B.trans[x][i])
continue;
int mid2=B.cnt_sg[B.trans[x][i]][27]-B.cnt_sg[B.trans[x][i]][A.sg[mida]];
if(mid2<k)
k-=mid2;
else{
bx[pos]='a'+i;
return dfsB(pos+1,B.trans[x][i]);
}
}
return -1;
}
signed main(){
scanf("%lld",&k);
scanf("%s",sa+1);
lena=strlen(sa+1);
scanf("%s",sb+1);
lenb=strlen(sb+1);
A.init(sa,lena);
B.init(sb,lenb);
if((mida=dfsA(1,1))==-1){
printf("NO\n");
return 0;
}
dfsB(1,1);
printf("%s\n",ax+1);
printf("%s\n",bx+1);
return 0;
}