CONSSTR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Alex Danilyuk
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Suffix Array, Dynamic Programming

PROBLEM:

Given a string s, we can perform the following operation on it:

  • Pick any non-empty suffix of s and append it to s

Given a string t, find the smallest string s such that performing this operation on s zero or more times gives t.

EXPLANATION:

First, note that s is going to be a suffix of t.

Knowing this, there is a fairly simple (but slow) dynamic programming solution as follows:
For 1\leq u\leq N, let dp_u be true if it is possible to start from the suffix of length u and end up at t after performing some operations. We are looking for the lowest value of u such that dp_u is true.
Note that dp_n is always true. Then, we can work in reverse:

dp[n] = true
for u from n-1 to 1:
	for each suffix S of t[0:u]:
		if t[0:u] + S == t[0:u+len(S)] and dp[u+len(S)] == true:
			set dp[u] = true

This runs in \mathcal{O}(N^3), which can be optimized to \mathcal{O}(N^2) with the help of suffix arrays and lcp:

  • Suppose we fix u < v such that dp_v is true.
  • Then, dp_u updates to true iff the longest common suffix of t[0:u] and t[0:v] is at least v-u.

This can be checked in \mathcal{O}(1) by building a suffix array on the reversed input string, then building the lcp array of that and querying it with a sparse table.
(The longest common suffix of two prefixes is equivalently the longest common prefix of two suffixes of the reversed string)
Henceforth, the longest common suffix of t[0:u] and t[0:v] will be denoted by l(u, v).

Let us analyze this further.
Upon fixing u, we want to find out whether there exists some v > u such that dp_v is true and l(u, v) \geq v-u.
Rewriting this, u\geq v - l(u, v), and the right side depends only on v once u is fixed.
So, we only care about the lowest possible value of v-l(u, v) among all v > u such that dp_v is true.

This now turns into a data structure problem, where we want to:

  1. Mark an index u as active
  2. Upon fixing an index u, find the minimum value of v - l(u, v) among all active v

There are multiple ways to achieve this in better than linear time, one will be presented below and a couple more mentioned.

We will use sqrt-decomposition on the queries, by maintaining a data structure that will be rebuild every time B \sim \sqrt{N} elements are not in it.

Suppose we iterate from n to 1. We only care about indices v such that dp_v is true.

At index u, there are two possibilities for such an index v:

  1. It is not in our data structure: there are at most B of these by assumption, we can check each one individually in \mathcal{O}(1) with lcp
  2. It is in the data structure, in which case we need to figure out how to find the minimum value of v - l(u, v) among the v in it.

Let us look at the suffix array we built.
Consider all v which are to the left of u in the suffix array (the case considering v to the right of u is symmetric).

Suppose v_1 > v_2 but v_1 appears before v_2 in the suffix array. Then, l(v_1, u) \leq l(v_2, u) so v_1 - l(v_1, u) > v_2 - l(v_2, u), so v_1 is functionally useless.

Thus, we only need to consider a sequence of increasing positions which also corresponds to an increasing sequence in the suffix array.

Now, suppose we move along the suffix array from left to right, considering this sequence of increasing positions.
For two positions v_1 < v_2, once we cross v_2, eventually v_2 will be useless because l(v_1, v) and l(v_2, v) will eventually be equal (or at least, l(v_2, v) will fall enough that v_1 - l(v_1, v) \leq v_2 - l(v_2, v)).
This observation lets us maintain a stack to find all the answers for all v in a similar manner to how CHT works, in \mathcal{O}(N) over all v.

Choosing B\sim \sqrt{N} means we rebuild the structure about \sqrt{N} times and each takes \mathcal{O}(N) time, and at each index we process \sim\sqrt{N} positions not in the structure, leading to a solution that is \mathcal{O}(N\sqrt{N}) overall.

ALTERNATE SOLUTIONS

Several other solutions are also possible:

  • The tester’s solution: the above approach, but instead of building any data structure, only consider those v to update u which are in [u+1, u+K] in the original string, or within K positions of the position of u in the suffix array for a fixed constant K.
    For K\geq \sqrt{N} it can be proved that this solution is correct.
  • A solution exists which builds HLD on a Suffix Automaton, code is attached below
  • It is possible to do \mathcal{O}(N^2/64) using bitsets, which turns out to run quite fast - several official solves used this.

TIME COMPLEXITY:

\mathcal{O}(N\sqrt N) or \mathcal{O}(N\log^2 N) depending on implementation.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int A = 30;
const int N = 500100;
const int LOG = 19;
char s[N];
bool dp[N];
int z[N];
int n;
int SA[N], nSA[N];
int ord[N], nord[N];
int a[N];
int revSA[N];
int LCP[N];
int sparse[LOG][N];
int p2[N];
int B;
int res[N];
pii st[N];
int pushMin[N];
int sz;

int getMin(int l, int r) {
	int k = p2[r - l];
	return min(sparse[k][l], sparse[k][r - (1 << k)]);
}
int getLCP(int x, int y) {
	if (x == y) return n - x;
	x = revSA[x]; y = revSA[y];
	if (x > y) swap(x, y);
	return getMin(x, y);
}

void buildSA() {
	for (int i = 0; i <= A; i++)
		a[i] = 0;
	for (int i = 0; i < n; i++) {
		a[(int)(s[i] + 2 - 'a')]++;
	}
	for (int i = 1; i < A; i++)
		a[i] += a[i - 1];
	for (int i = 0; i < n; i++)
		SA[a[(int)(s[i] + 1 - 'a')]++] = i;
	ord[SA[0]] = 0;
	for (int i = 1; i < n; i++) {
		ord[SA[i]] = ord[SA[i - 1]];
		if (s[SA[i]] != s[SA[i - 1]])
			ord[SA[i]]++;
	}
	for (int len = 1; ord[SA[n - 1]] != n - 1; len <<= 1) {
		for (int i = 0; i <= n; i++)
			a[i] = 0;
		for (int i = 0; i < n; i++) {
			int p = SA[i];
			int q = (p - len + n) % n;
			a[ord[q] + 1]++;
		}
		for (int i = 1; i <= n; i++)
			a[i] += a[i - 1];
		for (int i = 0; i < n; i++) {
			int p = SA[i];
			int q = (p - len + n) % n;
			nSA[a[ord[q]]++] = q;
		}
		nord[nSA[0]] = 0;
		for (int i = 1; i < n; i++) {
			int p1 = nSA[i], p2 = nSA[i - 1];
			int q1 = (p1 + len) % n, q2 = (p2 + len) % n;
			nord[p1] = nord[p2];
			if (ord[p1] != ord[p2] || ord[q1] != ord[q2]) nord[p1]++;
		}
		for (int i = 0; i < n; i++) {
			SA[i] = nSA[i];
			ord[i] = nord[i];
		}
	}
	for (int i = 0; i < n; i++)
		revSA[SA[i]] = i;
	int curLCP = 0;
	for (int i = 0; i < n; i++) {
		int p = revSA[i];
		if (p == n - 1) {
			curLCP = 0;
			continue;
		}
		curLCP = max(0, curLCP - 1);
		int q = SA[p + 1];
		while(i + curLCP < n && q + curLCP < n && s[i + curLCP] == s[q + curLCP]) curLCP++;
		LCP[p] = curLCP;
	}
	n--;
	for (int i = 0; i < n; i++)
		sparse[0][i] = LCP[i];
	for (int k = 0; k < LOG - 1; k++)
		for (int i = 0; i + (1 << (k + 1)) <= n; i++)
			sparse[k + 1][i] = min(sparse[k][i], sparse[k][i + (1 << k)]);
}

void updateStack() {
	while(sz > 1) {
		pushMin[sz - 2] = min(pushMin[sz - 2], pushMin[sz - 1]);
		st[sz - 2].second = min(st[sz - 2].second, pushMin[sz - 2]);
		if (st[sz - 2].first - st[sz - 2].second > st[sz - 1].first - st[sz - 1].second) break;
		sz--;
	}
}

void rebuild() {
	sz = 0;
	for (int i = 0; i <= n; i++) {
		if (sz > 0) {
			pushMin[sz - 1] = min(pushMin[sz - 1], LCP[i - 1]);
			st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
		}
		updateStack(); 
		int v = SA[i];
		if (v == n) continue;
		if (sz > 0) {
			st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
			res[v] = min(res[v], st[sz - 1].first - st[sz - 1].second);
		}
		if (!dp[n - v]) continue;
		while(sz > 0 && st[sz - 1].first > n - v) {
			sz--;
			if (sz > 0) {
				pushMin[sz - 1] = min(pushMin[sz - 1], pushMin[sz]);
				st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
			}
		}
		st[sz] = mp(n - v, n - v);
		pushMin[sz] = n + 1;
		sz++;
	}
	sz = 0;
	for (int i = n; i >= 0; i--) {
		if (sz > 0) {
			pushMin[sz - 1] = min(pushMin[sz - 1], LCP[i]);
			st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
		}
		updateStack(); 
		int v = SA[i];
		if (v == n) continue;
		if (sz > 0) {
			st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
			res[v] = min(res[v], st[sz - 1].first - st[sz - 1].second);
		}
		if (!dp[n - v]) continue;
		while(sz > 0 && st[sz - 1].first > n - v) {
			sz--;
			if (sz > 0) {
				pushMin[sz - 1] = min(pushMin[sz - 1], pushMin[sz]);
				st[sz - 1].second = min(st[sz - 1].second, pushMin[sz - 1]);
			}
		}
		st[sz] = mp(n - v, n - v);
		pushMin[sz] = n + 1;
		sz++;
	}
}

void solve() {
	scanf("%s", s);
	n = strlen(s);
	reverse(s, s + n);
	s[n++] = 'a' - 1;
	buildSA();
	for (int i = 0; i <= n; i++)
		dp[i] = 0;
	dp[n] = 1;
	B = 1;
	while(B * B < n / 4) B++;
	for (int i = 0; i < n; i++)
		res[i] = n + 1;
	vector<int> oks;
	oks.push_back(n);
	for (int i = n - 1; i > 0; i--) {
		if ((int)oks.size() == B) {
			rebuild();
			oks.clear();
		}
		dp[i] = res[n - i] <= i;
		for (int u : oks) {
			if (dp[i]) break;
			dp[i] |= u - getLCP(n - u, n - i) <= i;
		}
		if (dp[i]) oks.push_back(i);
	}
	int ans = 0;
	while(!dp[ans]) ans++;
	reverse(s, s + n);
	s[ans] = '\0';
	printf("%s\n", s);
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	for (int i = 2; i < N; i++)
		p2[i] = p2[i / 2] + 1;

	int t;
	scanf("%d", &t);
	while(t--) solve();

	return 0;
}
Setter's Solution (SAM + HLD)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int INF = (int)1e8;

struct SNode {
	int l, r;
	int minVal;
	int maxConst;
	int setTo;

	SNode() : l(), r(), minVal(INF), maxConst(0), setTo(-1) {}
	SNode(int _l, int _r) : l(_l), r(_r), minVal(INF), maxConst(0), setTo(-1) {}

	void set(int x) {
		setTo = x;
		minVal = x - maxConst;
	}
};
SNode tree[(1 << 21) + 3];
int L;
void build(int n) {
	L = max(2, n);
	while(L & (L - 1)) L++;
	for (int i = 0; i < L; i++)
		tree[L + i] = SNode(i, i + 1);
	for (int i = L - 1; i > 0; i--)
		tree[i] = SNode(tree[2 * i].l, tree[2 * i + 1].r);
}
void push(int v) {
	assert(v < L);
	if (tree[v].setTo == -1) return;
	for (int u = 2 * v; u < 2 * v + 2; u++) {
		tree[u].set(tree[v].setTo);
	}
	tree[v].setTo = -1;
}
void update(int v) {
	assert(v < L);
	tree[v].minVal = min(tree[2 * v].minVal, tree[2 * v + 1].minVal);
}
void setOnSegm(int v, int l, int r, int x) {
	if (l <= tree[v].l && tree[v].r <= r) {
		tree[v].set(x);
		return;
	}
	if (l >= tree[v].r || tree[v].l >= r) return;
	push(v);
	for (int u = 2 * v; u < 2 * v + 2; u++)
		setOnSegm(u, l, r, x);
	update(v);
}
int getMin(int v, int l, int r) {
	if (l <= tree[v].l && tree[v].r <= r) return tree[v].minVal;
	if (l >= tree[v].r || tree[v].l >= r) return INF;
	push(v);
	return min(getMin(2 * v, l, r), getMin(2 * v + 1, l, r));
}

const int N = 500100;
char s[N];
int n;
bool dp[N];
int vForPos[N];

struct Node {
	map<char, int> go;
	int suffLink;
	int len;

	Node() : go(), suffLink(-1), len(0) {}

	void eprint() {
		eprintf("[");
		for (auto t : go)
			eprintf("%c:%d,", t.first, t.second);
		eprintf("] link=%d, len=%d\n", suffLink, len);
	}
};
Node SA[2 * N];
int m;

int addChar(int v, char c) {
	int nv = m++;
	SA[nv].len = SA[v].len + 1;
	while(v != -1 && SA[v].go.count(c) == 0) {
		SA[v].go[c] = nv;
		v = SA[v].suffLink;
	}
	if (v == -1) {
		SA[nv].suffLink = 0;
		return nv;
	}
	int u = SA[v].go[c];
	if (SA[u].len == SA[v].len + 1) {
		SA[nv].suffLink = u;
		return nv;
	}
	int nu = m++;
	SA[nu] = SA[u];
	SA[u].suffLink = SA[nv].suffLink = nu;
	SA[nu].len = SA[v].len + 1;
	while(v != -1 && SA[v].go[c] == u) {
		SA[v].go[c] = nu;
		v = SA[v].suffLink;
	}
	return nv;
}
void buildSA() {
	while(m > 0) {
		m--;
		SA[m] = Node();
	}
	vForPos[0] = m++;
	for (int i = 0; i < n; i++)
		vForPos[i + 1] = addChar(vForPos[i], s[i]);
}

vector<int> g[2 * N];
int sz[2 * N];
int t[2 * N];
int prv[2 * N];
int h[2 * N];
int T;

void dfs1(int v) {
	sz[v] = 1;
	for (int u : g[v]) {
		h[u] = h[v] + 1;
		dfs1(u);
		sz[v] += sz[u];
	}
}
void dfs2(int v, int p) {
	t[v] = T++;
	prv[v] = p;
	int mx = 0;
	for (int u : g[v]) mx = max(mx, sz[u]);
	for (int u : g[v]) {
		if (sz[u] == mx) {
			dfs2(u, p);
			break;
		}
	}
	for (int u : g[v]) {
		if (sz[u] == mx) {
			mx = -1;
			continue;
		}
		dfs2(u, v);
	}
}

void buildHLD() {
	for (int i = 0; i < m; i++)
		g[i].clear();
	for (int i = 1; i < m; i++)
		g[SA[i].suffLink].push_back(i);
	T = 0;
	h[0] = 0;
	dfs1(0);
	dfs2(0, -1);
	build(m);
	for (int v = 0; v < m; v++)
		tree[L + t[v]].maxConst = SA[v].len;
	for (int i = L - 1; i > 0; i--)
		tree[i].maxConst = max(tree[2 * i].maxConst, tree[2 * i + 1].maxConst);
}

void activate(int v) {
	int x = v;
	v = vForPos[v];
	while(v != -1) {
		int u = prv[v];
		int r = t[v];
		int l;
		if (u == -1)
			l = r - h[v];
		else
			l = r - h[v] + h[u] + 1;
		r++;
		setOnSegm(1, l, r, x);
		v = u;
	}
}

bool check(int v) {
	eprintf("checking %d\n", v);
	int x = v;
	v = vForPos[v];
	while(v != -1) {
		int u = prv[v];
		int r = t[v];
		int l;
		if (u == -1)
			l = r - h[v];
		else
			l = r - h[v] + h[u] + 1;
		r++;
		int val = getMin(1, l, r);
		eprintf("segm %d %d\n", l, r);
		eprintf("val = %d\n", val);
		if (getMin(1, l, r) <= x) return true;
		v = u;
	}
	return false;
}

void solve() {
	scanf("%s", s);
	n = strlen(s);
	buildSA();
	for (int i = 0; i < m; i++) {
		eprintf("%d: ", i);
		SA[i].eprint();
	}
	for (int i = 0; i <= n; i++)
		dp[i] = 0;
	buildHLD();
	for (int i = 0; i < m; i++)
		eprintf("t[%d] = %d\n", i, t[i]);
	dp[n] = 1;
	activate(n);
	for (int i = n - 1; i > 0; i--) {
		eprintf("solving %d\n", i);
		dp[i] = check(i);
		if (dp[i]) activate(i);
	}
	int ans = 0;
	while(!dp[ans]) ans++;
	s[ans] = '\0';
	printf("%s\n", s);
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int t;
	scanf("%d", &t);
	while(t--) solve();

	return 0;
}


Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

void induced_sort(const vector<int> &vec, int val_range, vector<int> &SA, const vector<bool> &sl, const vector<int> &lms_idx) {
    vector<int> l(val_range, 0), r(val_range, 0);
    for (int c : vec) {
        if (c + 1 < val_range) ++l[c + 1];
        ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());
    fill(SA.begin(), SA.end(), -1);
    for (int i = lms_idx.size() - 1; i >= 0; --i)
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    for (int i : SA)
        if (i >= 1 && sl[i - 1]) {
            SA[l[vec[i - 1]]++] = i - 1;
        }
    fill(r.begin(), r.end(), 0);
    for (int c : vec)
        ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for (int k = SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
        if (i >= 1 && !sl[i - 1]) {
            SA[--r[vec[i - 1]]] = i - 1;
        }
}
 
vector<int> SA_IS(const vector<int> &vec, int val_range) {
    const int n = vec.size();
    vector<int> SA(n), lms_idx;
    vector<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
        sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
        if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vec, val_range, SA, sl, lms_idx);
    vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
        if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
            new_lms_idx[k++] = SA[i];
        }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
        int i = new_lms_idx[k - 1], j = new_lms_idx[k];
        if (vec[i] != vec[j]) {
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for (int a = i + 1, b = j + 1;; ++a, ++b) {
            if (vec[a] != vec[b]) {
                flag = true;
                break;
            }
            if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
                flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i)
        lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
        auto lms_SA = SA_IS(lms_vec, cur + 1);
        for (size_t i = 0; i < lms_idx.size(); ++i) {
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }
    induced_sort(vec, val_range, SA, sl, new_lms_idx);
    return SA;
}
vector<int> suffix_array(const string &s, const int LIM = 128) {
    vector<int> vec(s.size() + 1);
    copy(begin(s), end(s), begin(vec));
    vec.back() = '$';
    auto ret = SA_IS(vec, LIM);
    ret.erase(ret.begin());
    return ret;
}
 
 
 
vector<int> LCP(const string &s, const vector<int> &sa) {
    int n = s.size(), k = 0;
    vector<int> lcp(n), rank(n);
    for (int i = 0; i < n; i++)
        rank[sa[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])
            k++;
        lcp[rank[i]] = k;
    }
    lcp[n - 1] = 0;
    return lcp;
}

const int MAXN = 300050;
const int LOGN = 19;

int st[MAXN][LOGN];
int log_val[MAXN];
int sa_pos[MAXN];

int get_lcp(int a, int b){
	if(a>b) swap(a,b);
	int j = log_val[b-a+1];
	int lcp = min(st[a][j], st[b-(1<<j)+1][j]);
	return lcp;
}

int main(){
	fastio;

	int tests;
	cin >> tests;

	log_val[1] = 0;
	for(int i = 2; i < MAXN; i++){
		log_val[i] = log_val[i/2] + 1;
	}
    const int del = 800;

	while(tests--){
	
		string s; 
		cin >> s;

		int n = s.length();

		int del2 = 2 * n / del + 2;

		for(int i = 0; i < n; i++){
			sa_pos[i] = 0;
			for(int j = 0; j < min(LOGN, log_val[n]+1); j++){
				st[i][j] = 1e9+7;
			}
		}

		reverse(s.begin(), s.end());

		vector<int> sa = suffix_array(s);
		vector<int> lcp = LCP(s, sa);

		for(int i = 0; i < n; i++){
			st[i][0] = lcp[i];
			sa_pos[sa[i]] = i;
		}
		for(int j = 1; j < LOGN; j++){
			for(int i = 0; i + (1<<(j-1)) < n; i++){
				st[i][j] = min(st[i][j-1], st[i + (1<<(j-1))][j-1]);
			}
		}

		bool done[n] = {0};
		done[0] = 1;
		int last = 0;

		for(int i = 0; i < n; i++){
			if(!done[i]) continue;

			int val_pos = sa_pos[i];
			int curLCP = n - i;
			for (int j = 1; j <= val_pos && j <= del2; j++) {
				curLCP = min(curLCP, lcp[val_pos - j]);
				int q = sa[val_pos - j];
				if(q<=i) continue;
				if(i+curLCP>=q){
					done[q] = 1;
					last = max(last, q);
				}
			}
			curLCP = n - i;
			for (int j = 1; val_pos + j < n && j <= del2; j++) {
				curLCP = min(curLCP, lcp[val_pos + j - 1]);
				int q = sa[val_pos + j];
				if(q<=i) continue;
				if(i+curLCP>=q){
					done[q] = 1;
					last = max(last, q);
				}
			}
			
			for(int j = i+1; j < min(n, i+del+1); j++){
				int a1 = sa_pos[i];
				int a2 = sa_pos[j];
				if(a1>a2) swap(a1,a2);
				a2--;
				int l = get_lcp(a1,a2);
				if(i+l>=j){
					done[j] = 1;
					last = max(last, j);
				}
			}
		}

		for(int i = n-1; i >= last; i--){
			cout << s[i];
		}
		cout << endl;
	}

	return 0;
}
2 Likes