# O((m+n)^2) with linear time suffix array construction

• ``````#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )

namespace KoAluru
{
bool *t;
int *b;

template<typename T>
void bucket(T a[], int n, int k, bool end)
{
fill_n(b, k, 0);
REP(i, n) b[a[i]]++;
if (end)
FOR(i, 1, k)
b[i] += b[i-1];
else {
int s = 0;
REP(i, k)
s += b[i], b[i] = s-b[i];
}
}

template<typename T>
void plus_to_minus(T a[], int sa[], int n, int k)
{
bucket(a, n, k, false);
sa[b[a[n-1]]++] = n-1;
REP(i, n-1) {
int j = sa[i]-1;
if (j >= 0 && ! t[j])
sa[b[a[j]]++] = j;
}
}

template<typename T>
void minus_to_plus(T a[], int sa[], int n, int k)
{
bucket(a, n, k, true);
ROF(i, 0, n) {
int j = sa[i]-1;
if (j >= 0 && t[j])
sa[--b[a[j]]] = j;
}
}

template<typename T>
void ka(const T a[], int n, int k, int sa[])
{
t[n-1] = false;
ROF(i, 0, n-1)
t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1];
bool minor = 2 * count(t, t+n, false) > n;

bucket(a, n, k, minor);
fill_n(sa, n, -1);
if (minor) {
REP(i, n)
if (t[i])
sa[--b[a[i]]] = i;
plus_to_minus(a, sa, n, k);
minus_to_plus(a, sa, n, k);
} else {
sa[b[a[n-1]]++] = n-1;
REP(i, n-1)
if (! t[i])
sa[b[a[i]]++] = i;
minus_to_plus(a, sa, n, k);
plus_to_minus(a, sa, n, k);
}

int last = -1, name = 0, nn = count(t, t+n, minor);
int *sa2, *pi;
if (minor)
sa2 = sa, pi = sa+n-nn;
else
sa2 = sa+n-nn, pi = sa;
fill_n(b, n, -1);
REP(i, n)
if (sa[i] >= 0 && minor == t[sa[i]]) {
bool diff = last == -1;
int p = sa[i];
if (! diff)
REP(j, n) {
if (last+j >= n || p+j >= n || a[last+j] != a[p+j] || t[last+j] != t[p+j]) {
diff = true;
break;
} else if (j > 0 && (minor == t[last+j] || minor == t[p+j]))
break;
}
if (diff) {
name++;
last = p;
}
b[p] = name-1;
}
nn = 0;
REP(i, n)
if (b[i] >= 0)
pi[nn++] = b[i];

if (name < nn)
ka(pi, nn, name, sa2);
else
REP(i, nn)
sa2[pi[i]] = i;

ROF(i, 0, nn)
t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1];

nn = 0;
bucket(a, n, k, minor);
if (minor) {
REP(i, n)
if (minor == t[i])
pi[nn++] = i;
REP(i, nn)
sa[i] = pi[sa2[i]];
ROF(i, 0, nn) {
int j = sa[i];
sa[i] = -1;
sa[--b[a[j]]] = j;
}
} else {
REP(i, n)
if (minor == t[i])
pi[nn++] = i;
ROF(i, 0, nn)
sa[n-nn+i] = pi[sa2[i]];
REP(i, nn) {
int j = sa[n-nn+i];
sa[n-nn+i] = -1;
sa[b[a[j]]++] = j;
}
}
if (minor)
plus_to_minus(a, sa, n, k);
else
minus_to_plus(a, sa, n, k);
}

template<typename T>
void main(const T a[], int n, int k, int sa[], int b[])
{
if (n > 0) {
KoAluru::b = b;
t = new bool[n];
ka(a, n, k, sa);
delete[] t;
}
}
};

class Solution {
vector<int> maxSubseq(const vector<int> &a, int c) {
vector<int> r;
REP(i, a.size()) {
while (r.size()+a.size()-i > c && r.size() && r.back() < a[i])
r.pop_back();
if (r.size() < c)
r.push_back(a[i]);
}
return r;
}
vector<int> interleave(vector<int> a, const vector<int> &b) {
int m = a.size(), n = b.size(), i = 0, j = 0, k = 0;
vector<int> sa(m+n+1), rnk(max(m+n+1, 10+1));
a.resize(m+n+1);
REP(i, m)
a[i]++;
a[m] = 0;
REP(i, n)
a[m+1+i] = b[i]+1;
KoAluru::main(&a[0], m+n+1, 10+1, &sa[0], &rnk[0]);
REP(i, m+n+1)
rnk[sa[i]] = i;
while (i < m || j < n)
if (j == n || i < m && rnk[i] > rnk[m+1+j])
sa[k++] = a[i++]-1;
else
sa[k++] = b[j++];
sa.pop_back();
return sa;
}
public:
vector<int> maxNumber(vector<int> &a, vector<int> &b, int k) {
int m = a.size(), n = b.size();
vector<int> mx;
for (int i = max(k-n, 0); i <= min(k, m); i++) {
auto t = interleave(maxSubseq(a, i), maxSubseq(b, k-i));
if (lexicographical_compare(mx.begin(), mx.end(), t.begin(), t.end()))
mx.swap(t);
}
return mx;
}
};
``````