Two Strings Game

                            Solution in C :

In   C++  :







#include <bits/stdc++.h>

using namespace std;

const int maxn = 6e5;

string ans;
int mex_ans;

struct suffix_automaton
{
    int len[maxn], link[maxn];
    map<char, int> to[maxn];
    int sz = 1, last;
    void add_letter(char c)
    {
        int p = last;
        last = sz++;
        len[last] = len[p] + 1;
        for(; !to[p][c]; p = link[p]) to[p][c] = last;
        if(to[p][c] == last)
            return;
        int q = to[p][c];
        if(len[q] == len[p] + 1)
        {
            link[last] = q;
            return;
        }
        int cl = sz++;
        to[cl] = to[q];
        link[cl] = link[q];
        len[cl] = len[p] + 1;
        link[last] = link[q] = cl;
        for(; to[p][c] == q; p = link[p]) to[p][c] = cl;
    }

    vector<int> top_sort[maxn];
    int mex[maxn];
    int mex_d[maxn];
    int64_t total[maxn];
    int64_t sum;

    void dfs()
    {
        for(auto it: top_sort)
        for(auto v: it)
        {
            vector<int> g;
            for(auto it: to[v])
                g.push_back(mex[it.second]);
            for(auto it: g)
                mex_d[it] = v + 1;
            for(int i = 0; ; i++)
                if(mex_d[i] != v + 1)
                {
                    mex[v] = i;
                    break;
                }
            if(v == 0)
            {
                total[mex[v]]++;
                sum++;
            }
            total[mex[v]] += len[v] - len[link[v]];
            sum += len[v] - len[link[v]];
        }
    }

    void build(string s)
    {
        for(auto c: s)
            add_letter(c);
        for(int i = 0; i < sz; i++)
            top_sort[len[i]].push_back(i);
        reverse(top_sort, top_sort + maxn);
        dfs();
    }

    int64_t win[maxn];
    int64_t win_cnt[maxn];

    void rec_dfs(int v, int64_t &k)
    {
        if(win[v] >= k)
        {
            mex_ans = mex[v];
            return;
        }
        else
        {
            k -= win[v];
        }
        for(auto it: to[v])
        {
            if(win_cnt[it.second] >= k)
            {
                ans += it.first;
                rec_dfs(it.second, k);
                return;
            }
            else
            {
                k -= win_cnt[it.second];
            }
        }
    }
} sa1, sa2;

const int64_t inf = 1e18 + 42;
void win_dfs1()
{
    for(auto it: sa1.top_sort)
    for(auto v: it)
    {
        sa1.win[v] = sa2.sum - sa2.total[sa1.mex[v]];
        sa1.win_cnt[v] = sa1.win[v];
        for(auto it: sa1.to[v])
        {
            sa1.win_cnt[v] += sa1.win_cnt[it.second];
            sa1.win_cnt[v] = min(sa1.win_cnt[v], inf);
        }
    }
}

void win_dfs2()
{
    for(auto it: sa2.top_sort)
    for(auto v: it)
    {
        sa2.win[v] = mex_ans != sa2.mex[v];
        sa2.win_cnt[v] = sa2.win[v];
        for(auto it: sa2.to[v])
            sa2.win_cnt[v] += sa2.win_cnt[it.second];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    int64_t k;
    cin >> n >> m >> k;
    string a, b;
    cin >> a >> b;
    sa1.build(a);
    sa2.build(b);
    win_dfs1();
    if(k > sa1.win_cnt[0])
    {
        cout << "no solution" << endl;
        return 0;
    }
    sa1.rec_dfs(0, k);
    cout << ans << endl;
    win_dfs2();
    ans = "";
    sa2.rec_dfs(0, k);
    cout << ans << endl;
    return 0;
}









In   Java  :







import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";


static class Result
{
int[] sa;
int[] lcp;
int[][] branches;
long[] count;
int[] zero, one;
int[] deadline;

public Result(int[] sa, int[] lcp,
int[][] branches, long[] count,
int[] zero, int[] one, int[] deadline) {
this.sa = sa;
this.lcp = lcp;
this.branches = branches;
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}

static void solve()
{
int n = ni(), m = ni();
long K = nl();
char[] a = ns(n);
char[] b = ns(m);

Result ra = go(a);
Result rb = go(b);
long[] ca = ra.count;
long[] cb = rb.count;
if(cb.length < ca.length){
cb = Arrays.copyOf(cb, ca.length);
}
long totcb = 0;
for(long v : cb)totcb += v;

Arrays.sort(ra.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});

K--;

// ""
{
long lcount = totcb - cb[ra.branches[0][3]];
if(K < lcount){
int[] resb = kth(rb, K, ra.branches[0][3]);

out.println("");
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= lcount;
}
}

int bp = 0;

bp++;
for(int i = 0;i < n;i++){

long lcount = 0;
lcount += ra.zero[i] * (totcb - cb[0]);
lcount += ra.one[i] * (totcb - cb[1]);
int obp = bp;
while(bp < ra.branches.length && ra.branches[bp][0] == i){
lcount += totcb - cb[ra.branches[bp][3]];
bp++;
}

if(K < lcount){

int[] row = new int[n-ra.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[ra.branches[j][2]-1] = ra.branches[j][3];
}
for(int j = n-ra.sa[i]-1;j >= ra.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-ra.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}

for(int j = ra.deadline[i]+1;j < n-ra.sa[i];j++){
long llcount = totcb - cb[row[j]];
if(K < llcount){

int[] resa = new int[]{ra.sa[i], j+1};
int[] resb = kth(rb, K, row[j]);

out.println(new String(a, resa[0], resa[1]));
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= llcount;
}
}
}else{
K -= lcount;
}
}

out.println("no solution");
}

static int[] kth(Result rb, long K, int proh)
{
Arrays.sort(rb.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});


if(rb.branches[0][3] != proh){
if(K == 0){
return new int[]{0, 0};
}else{
K--;
}
}

int n = rb.sa.length;
int bp = 1;
for(int i = 0;i < n;i++){
// row
long lcount = 0;
if(proh != 0)lcount += rb.zero[i];
if(proh != 1)lcount += rb.one[i];
int obp = bp;
while(bp < rb.branches.length && rb.branches[bp][0] == i){
if(proh != rb.branches[bp][3])lcount++;
bp++;
}
if(K < lcount){

int[] row = new int[n-rb.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[rb.branches[j][2]-1] = rb.branches[j][3];
}
for(int j = n-rb.sa[i]-1;
j >= rb.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-rb.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}

for(int j = rb.deadline[i]+1;
j < n-rb.sa[i];j++){
if(row[j] != proh){
if(K == 0){
return new int[]{rb.sa[i], j+1};
}
K--;
}
}
}else{
K -= lcount;
}
}
return null;
}

static Result go(char[] a)
{
int[] sa = suffixsort(a);
int[] lcp = buildLCP(a, sa);

int[][] branches = findBranches(lcp);


LResult lres = countNimber(sa, lcp, branches);

return new Result(sa, lcp, branches, 
lres.count, lres.zero, lres.one, lres.deadline);
}

private static LResult countNimber(int[] sa,

 int[] lcp, int[][] branches)
{
int n = sa.length;

int[] zero = new int[n];
int[] one = new int[n];
int[] deadline = new int[n];
Arrays.fill(deadline, -1);


int[] hs = new int[n];
int[] nim = new int[n];
Arrays.fill(nim, -1);
long[] count = new long[n+1];
for(int i = 0;i < n;i++){
hs[i] = n-sa[i]+1;
}
int[] alive = new int[n];
Arrays.fill(alive, 1);
int[] ftalive = buildFenwick(alive);
int bp = 0;
int[] bs2 = new int[n];
for(int[] branch : branches){
int sp = 0;
int L = branch[0];
int R = branch[1];
int h = branch[2];

if(L == -1)L = 0;
int bs = 0;

for(int i = L;i <= R && i >= 0;
i = after(ftalive, i)){

if(nim[i] >= 0)count[nim[i]]++;
int bet = hs[i]-h-1;

if(nim[i] == 0){
count[0] += bet / 2;
count[1] += (bet+1)/2;
zero[i] += bet/2;
one[i] += (bet+1)/2;
// 0|10|1
bs |= 1<<(bet&1);
}else{
count[0] += (bet+1) / 2;
count[1] += bet/2;
zero[i] += (bet+1)/2;
one[i] += bet/2;
if(bet == 0){
if(nim[i] >= 0){
if(nim[i] <= 31){
bs |= 1<<nim[i];
}else{
bs2[sp++] = nim[i];
}
}
}else{
bs |= 1<<((bet&1)^1);
}
}
hs[i] = h;

if(i > L){
// kill
alive[i] = 0;
deadline[i] = h-1;
addFenwick(ftalive, i, -1);
}
}

int clus = Integer.numberOfTrailingZeros(~bs);
if(clus >= 32){
Arrays.sort(bs2, 0, sp);
clus = 32;
for(int q = 0;q < sp;){
if(bs2[q] == clus){
while(q < sp && bs2[q] == clus)q++;
clus++;
}else{
break;
}
}
}

branches[bp++][3] = nim[L] = clus;
if(branch[0] == -1)count[nim[L]]++;
}


return new LResult(count, zero, one, deadline);
}

static class LResult
{
long[] count;
int[] zero, one;
int[] deadline;
public LResult(long[] count, int[] zero, 
int[] one, int[] deadline) {
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}


static int[][] findBranches(int[] a)
{
int n = a.length;
long[] ap = new long[n];
for(int i = 0;i < n;i++)ap[i] = (long)(1000000-a[i])<<32|i;
Arrays.sort(ap);
int[][] branches = new int[n][];


int p = 0;
int[] flag = new int[n];
Arrays.fill(flag, 1);
int[] ft = buildFenwick(flag);
for(int i = 0;i < n;i++){
int j;
int last = (int)ap[i];
int va = 1000000-(int)(ap[i]>>>32);
for(j = (int)ap[i];j >= 0 && j < n && 
flag[j] == 1 && a[j] >= va;j = after(ft, j)){ 
last = j;
flag[j] = 0;
addFenwick(ft, j, -1);
}

if(j == (int)ap[i])continue;

branches[p++] = new int[]
{before(ft, (int)ap[i]), last, va, -1};

}
return Arrays.copyOf(branches, p);
}

public static int sumFenwick(int[] ft, int i)
{
int sum = 0;
for(i++;i > 0;i -= i&-i)sum += ft[i];
return sum;
}

public static void addFenwick(int[] ft, int i, int v)
{
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i)ft[i] += v;
}

public static int findGFenwick(int[] ft, int v)
{
int i = 0;
int n = ft.length;
for(int b = Integer.highestOneBit(n);
b != 0 && i < n;b >>= 1){
if(i + b < n){
int t = i + b;
if(v >= ft[t]){
i = t;
v -= ft[t];
}
}
}
return v != 0 ? -(i+1) : i-1;
}

public static int valFenwick(int[] ft, int i)
{
return sumFenwick(ft, i) - sumFenwick(ft, i-1);
}

public static int[] restoreFenwick(int[] ft)
{
int n = ft.length-1;
int[] ret = new int[n];
for(int i = 0;i < n;i++)ret[i] = sumFenwick(ft, i);
for(int i = n-1;i >= 1;i--)ret[i] -= ret[i-1];
return ret;
}

public static int before(int[] ft, int x)
{
int u = sumFenwick(ft, x-1);
if(u == 0)return -1;
return findGFenwick(ft, u-1)+1;
}

public static int after(int[] ft, int x)
{
int u = sumFenwick(ft, x);
int f = findGFenwick(ft, u);
if(f+1 >= ft.length-1)return -1;
return f+1;
}

public static int[] buildFenwick(int[] a)
{
int n = a.length;
int[] ft = new int[n+1];
System.arraycopy(a, 0, ft, 1, n);
for(int k = 2, h = 1;k <= n;k*=2, h*=2){
for(int i = k;i <= n;i+=k){
ft[i] += ft[i-h];
}
}
return ft;
}


public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] b = new int[n];
for(int i = 0;i < n;i++)b[sa[i]] = i;
for(int i = 0;i < n;i++){
if(b[i] > 0){
for(int j = sa[b[i]-1]; j+h<n && 
i+h<n && str[j+h] == str[i+h]; h++);
lcp[b[i]] = h;
}else{
lcp[b[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}    

private static interface BaseArray {
public int get(int i);

public void set(int i, int val);

public int update(int i, int val);
}

private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;

CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}

public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}

public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}

public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}

private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;

IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}

public int get(int i) {
return m_A[m_pos + i];
}

public void set(int i, int val) {
m_A[m_pos + i] = val;
}

public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}


private static void getCounts(BaseArray T, 
BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}

private static void getBuckets(BaseArray C,
 BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}

/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T,
int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); 
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); 
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}

private static int LMSpostproc(BaseArray T, 
int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;


for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}


i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}


for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}

return name;
}

private static void induceSA(BaseArray T, int[] SA,
 BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); 
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}


private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;

if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}


getCounts(T, C, n, k);
getBuckets(C, B, k, true); 
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}


if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;

i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}

for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}


if((flags & 8) != 0){
getCounts(T, C, n, k);
}

if(1 < m){
getBuckets(C, B, k, true); 
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}

/* char */
public static int[] suffixsort(char[] T) {
if(T == null)return null;
int n = T.length;
int[] SA = new int[n];
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return SA;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 65536);
return SA;
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in :
 new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))
return false;

try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); }
 catch (IOException e)
  { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c) 
{ return !(c >= 33 && c <= 126); }
private static int skip() 
{ int b; 
while((b = readByte()) != -1 && isSpaceChar(b)); 
return b; }

private static double nd() { return Double.parseDouble(ns()); }
private static char nc()
 { return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !(
    (b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !(
    (b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static void tr(Object... o) 
{ if(INPUT.length() != 0)
System.out.println(Arrays.deepToString(o)); }
}










In  C  :








#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
int x;
unsigned long long count;
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
int dfs0(st_node *root,int flag);
unsigned long long dfs1(st_node *root);
void dfs2(int idx,st_node *root);
unsigned long long dfs3(st_node *root);
void dfs4(int idx,st_node *root);
void suffix_tree(st_node *root,char *str,int len);
char a[300001],b[300001],ans[300001];
unsigned long long dp[50],total,K,KK,val;

int main(){
int N,M,i;
st_node r1,r2;
scanf("%d%d%lld%s%s",&N,&M,&K,a,b);
suffix_tree(&r1,a,N);
suffix_tree(&r2,b,M);
dfs0(&r1,0);
dfs0(&r2,1);
for(i=0;i<50;i++)
total+=dp[i];
dfs1(&r1);
if(r1.count<K){
printf("no solution\n");
return 0;
}
dfs2(0,&r1);
dfs3(&r2);
KK=0;
dfs4(0,&r2);
return 0;
}
int dfs0(st_node *root,int flag){
char arr[20];
int len,ret,i;
if(!root){
if(flag)
dp[0]++;
return 0;
}
memset(arr,0,sizeof(arr));
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret=dfs0(root->edges[i]->node,flag);
if(len==1)
arr[ret]=1;
else
if(ret){
if(flag){
dp[0]+=len/2;
dp[1]+=(len-1)/2;
}
if(len%2)
arr[1]=1;
else
arr[0]=1;
}
else{
if(flag){
dp[1]+=len/2;
dp[0]+=(len-1)/2;
}
if(len%2)
arr[0]=1;
else
arr[1]=1;
}
}
for(i=0;i<20 && arr[i];i++);
if(flag)
dp[i]++;
root->x=i;
return i;
}
unsigned long long dfs1(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root)
return total-dp[0];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs1(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
count+=len/2*(total-dp[0]);
count+=(len-1)/2*(total-dp[1]);
}
else{
count+=len/2*(total-dp[1]);
count+=(len-1)/2*(total-dp[0]);
}
}
count+=total-dp[root->x];
root->count=count;
return count;
}
void dfs2(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
val=0;
K-=KK;
return;
}
if(KK+total-dp[root->x]>=K){
ans[idx]=0;
printf("%s\n",ans);
val=root->x;
K-=KK;
return;
}
KK+=total-dp[root->x];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
t2=total-dp[0];
}
t1=0;
if(ret){
t1+=len/2*(total-dp[0]);
t1+=(len-1)/2*(total-dp[1]);
}
else{
t1+=len/2*(total-dp[1]);
t1+=(len-1)/2*(total-dp[0]);
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=a[j];
dfs2(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[
i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=a[j];
if(KK+total-dp[start]>=K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
val=start;
K-=KK;
return;
}
KK+=total-dp[start];
}
return;
}
}
return;
}
unsigned long long dfs3(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root){
if(val)
return 1;
return 0;
}
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs3(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
if(val!=0)
count+=len/2;
if(val!=1)
count+=(len-1)/2;
}
else{
if(val!=1)
count+=len/2;
if(val!=0)
count+=(len-1)/2;
}
}
if(val!=root->x)
count++;
root->count=count;
return count;
}
void dfs4(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x && KK+1==K){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x)
KK++;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
if(val)
t2=1;
else
t2=0;
}
t1=0;
if(ret){
if(val!=0)
t1+=len/2;
if(val!=1)
t1+=(len-1)/2;
}
else{
if(val!=1)
t1+=len/2;
if(val!=0)
t1+=(len-1)/2;
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[
i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=b[j];
dfs4(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=b[j];
if(val!=start){
if(KK+1==K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
return;
}
KK++;
}
}
return;
}
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[
a_edge]->from+a_len]==str[i])
if(a_node->edges[
a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[
str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[
    str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[
    a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[
    a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[
    a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}