#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
char a[maxn],b[maxn],ans1[maxn],ans2[maxn];
ll k,res;
struct SAM
{
    int fa[maxn],zi[maxn][26],len[maxn],c[maxn],rk[maxn];
    ll id,ed,sg[maxn],cnt[maxn][27],sum[maxn];
    SAM() 
    {
        id = ed = 1;
        memset( c,0,sizeof c );
        memset( rk,0,sizeof rk ); 
        memset( fa,0,sizeof fa ); 
        memset( zi,0,sizeof zi );
        memset( len,0,sizeof len );
        memset( sg,-1,sizeof sg );
        memset( cnt,0,sizeof cnt );
        memset( sum,0,sizeof sum );
    }
    void insert(int c)
    {
        int p = ed, np = ++id; ed = id;
        len[np] = len[p]+1;
        for( ;p&&!zi[p][c];p=fa[p] )    zi[p][c] = np;
        if( !p )    fa[np] = 1;
        else
        {
            int q = zi[p][c];
            if( len[q]==len[p]+1 )    fa[np] = q;
            else
            {
                int nq = ++id;
                memcpy( zi[nq],zi[q],sizeof zi[nq] );
                fa[nq] = fa[q], len[nq] = len[p]+1;
                fa[np] = fa[q] = nq;
                for( ;p&&zi[p][c]==q;p=fa[p] )    zi[p][c] = nq;
            }
        }
    }
    int getsg(int u)
    {
        if( sg[u]!=-1 )    return sg[u]; 
        int ok[27]; memset( ok,0,sizeof ok );
        for(int i=0,v;i<=25;i++)
        {
            if( !(v=zi[u][i]) )    continue;
            ok[getsg(v)] = 1;
        }
        for(int i=0;;i++)
            if( ok[i]==0 )    return sg[u] = i;
    }
    void init(int u)
    {
        if( sum[u] )    return;
        for(int i=0,v;i<=25;i++)
        {
            if( !(v=zi[u][i]) )    continue;
            init(v);
            for(int j=0;j<=26;j++)    cnt[u][j] += cnt[v][j];
        }
        cnt[u][sg[u]]++;
        for(int i=0;i<=26;i++)    sum[u] += cnt[u][i];
    }
    void build( char a[] )
    {
        int len = strlen( a+1 );
        for(int i=1;i<=len;i++)    insert( a[i]-'a' );
        getsg(1); init(1);
    }
}sa,sb;
int dfs1(int x,int pos)
{
    ll sum1 = sb.sum[1]-sb.cnt[1][sa.sg[x]];//当前节点获胜的方案数 
    if( sum1>=k )    return x;
    else    k -= sum1;
    for(int i=0,v;i<26;i++)
    {
        if( !(v=sa.zi[x][i]) )    continue;
        ll sum2 = sa.sum[v]*sb.sum[1];
        for(int j=0;j<=26;j++)
            sum2 -= sa.cnt[v][j]*sb.cnt[1][j];
        if( sum2<k )    k-=sum2;
        else
        {
            ans1[pos] = 'a'+i;
            return dfs1( v,pos+1 );    
        }    
    }
    return -1;    
}
void dfs2(int x,int pos)
{
    k -= ( sa.sg[res]!=sb.sg[x] );
    if( k==0 )    return;
    for(int i=0,v;i<26;i++)
    {
        if( !(v=sb.zi[x][i] ) )    continue;
        ll sum = sb.sum[v]-sb.cnt[v][sa.sg[res]];
        if( sum<k )    k-=sum;
        else
        {
            ans2[pos] = 'a'+i;
            dfs2(v,pos+1); return;
        }
    }
}
int main()
{
    scanf("%lld%s%s",&k,a+1,b+1);
    sa.build(a); sb.build(b);
    res = dfs1(1,1);
    if( res==-1 )    puts("NO");
    else
    {
        dfs2(1,1);
        printf("%s\n%s",ans1+1,ans2+1);
    }
}
最后修改:2022 年 01 月 09 日 02 : 18 PM