1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
const int N = 6E5 + 100;
struct SAM {
int t[N][26], len[N] = {-1}, fa[N], sz = 2, last = 1;
void ins(int ch) {
int p = last, np = last = sz++;
len[np] = len[p] + 1;
for (; p && !t[p][ch]; p = fa[p]) t[p][ch] = np;
if (!p) { fa[np] = 1; return; }
int q = t[p][ch];
if (len[p] + 1 == len[q]) fa[np] = q;
else {
int nq = sz++; len[nq] = len[p] + 1;
memcpy(t[nq], t[q], sizeof t[0]);
fa[nq] = fa[q];
fa[np] = fa[q] = nq;
for (; t[p][ch] == q; p = fa[p]) t[p][ch] = nq;
}
}
int sg[N];
__int128 cnt[N], csg[27];
int go(int u = 1, int d = 0) {
int& ret = sg[u];
if (ret != -1) return ret;
cnt[u] = 1;
int F = 0;
FOR (c, 0, 26)
if (t[u][c]) {
F |= 1 << go(t[u][c], d + 1);
cnt[u] += cnt[t[u][c]];
}
ret = 0;
while (F & (1 << ret)) ++ret;
csg[ret] += len[u] - len[fa[u]];
return ret;
}
} a, b;
LL K;
__int128 cw1[N];
void init1(int u) {
if (cw1[u] != -1) return;
cw1[u] = b.cnt[1] - b.csg[a.sg[u]];
FOR (c, 0, 26) {
int v = a.t[u][c]; if (!v) continue;
init1(v); cw1[u] += cw1[v];
}
}
int SG;
void go1(int u, int c) {
LL t = b.cnt[1] - b.csg[a.sg[u]];
if (c != -1) putchar(c + 'a');
if (K <= t) { SG = a.sg[u]; return; }
K -= t;
FOR (c, 0, 26) {
int v = a.t[u][c]; if (!v) continue;
if (cw1[v] < K) K -= cw1[v];
else { go1(v, c); return; }
}
}
__int128 cw2[N];
void init2(int u) {
if (cw2[u] != -1) return;
cw2[u] = b.sg[u] != SG;
FOR (c, 0, 26) {
int v = b.t[u][c]; if (!v) continue;
init2(v); cw2[u] += cw2[v];
}
}
void go2(int u, int c) {
LL t = b.sg[u] != SG;
if (c != -1) putchar(c + 'a');
if (K <= t) return;
K -= t;
FOR (c, 0, 26) {
int v = b.t[u][c]; if (!v) continue;
if (cw2[v] < K) K -= cw2[v];
else { go2(v, c); return; }
}
}
char sa[N], sb[N];
int main() {
#ifdef zerol
freopen("inin", "r", stdin);
#endif
memset(a.sg, -1, sizeof a.sg); memset(b.sg, -1, sizeof b.sg);
memset(cw1, -1, sizeof cw1); memset(cw2, -1, sizeof cw2);
int la, lb; scanf("%d%d%lld%s%s", &la, &lb, &K, sa, sb);
FOR (i, 0, la) a.ins(sa[i] - 'a');
FOR (i, 0, lb) b.ins(sb[i] - 'a');
dbg(b.t[1][2]);
a.go(); b.go();
__int128 all = 0;
FOR (i, 1, a.sz)
all += (a.len[i] - a.len[a.fa[i]]) * (b.cnt[1] - b.csg[a.sg[i]]);
if (K > all) { puts("no solution"); return 0; }
init1(1);
go1(1, -1); puts("");
init2(1);
go2(1, -1); puts("");
}
|