Skip to Content
CTRL K

Clarkson

La solución tiene dos partes:

  1. Hallar el arreglo FF tal que la subcadena S[i:i+Fi]S[i:i + F_i] es una subcadena de TT y FiF_i es maximal.
  2. Búsqueda binaria de la respuesta.

Parte 1 - Hallar FF

Esta es la parte más difícil del problema. La resolveremos con un arreglo de sufijos y LCP.

Primero, concatenamos SS y TT con un carácter ~ y construimos el arreglo de sufijos de la cadena resultante. Con ese arreglo de sufijos construimos el arreglo LCP. (Si no se conoce esta técnica, ver este curso de Codeforces .)

Recordemos que el LCP de dos sufijos es el mínimo de rango de los elementos del arreglo LCP entre esos dos sufijos.

Como queremos que FiF_i sea maximal, solo hace falta revisar dos sufijos para cada ii: ¡los dos sufijos más cercanos al sufijo que empieza en S[i]S[i]! Podemos hallar los índices de esos dos sufijos con un std::set.

Esta parte del algoritmo corre en tiempo O((N+M)log⁡(N+M))\mathcal{O}((N + M) \log (N + M)) (pero construcciones más lentas del arreglo de sufijos también pasan).

Parte 2 - Búsqueda binaria

La búsqueda binaria funciona porque si podemos lograr una longitud mínima ll, entonces también podemos lograr una longitud mínima k<lk < l (ya que no necesariamente necesitamos una subcadena de longitud kk; solo necesitamos que las longitudes de todas las subcadenas sean de longitud al menos kk).

Así comprobamos si podemos lograr una cierta longitud mínima ll:

Sea dp[i]dp[i] si podemos formar S[i:N]S[i : N] usando subcadenas de TT de tamaño al menos ll. Claramente, si dp[j]dp[j] es verdadero para algún j∈[i+l,i+Fi]j \in [i + l, i + F_i], entonces dp[i]dp[i] también es verdadero.

Para comprobar si existe tal jj, podemos guardar todos los índices donde dp[j]dp[j] es verdadero en un conjunto y revisar si alguno cae en el rango [i+l,i+Fi][i + l, i + F_i].

Esta parte del algoritmo corre en tiempo O(Nlog⁡2N)\mathcal{O}(N \log^2 N) (o O(Nlog⁡N)\mathcal{O}(N \log N) si hacemos la comprobación en O(N)\mathcal{O}(N)).

Implementación

#include <bits/stdc++.h>
using namespace std;
 
string s, t, u;
int n, m, l;
int ord[200005], nord[200005], suff[200005], rev[200005], p = 1;
int lcp[200005][20], match[100000], h = 0;
set<int> topgear;
 
void build_suffix_arr() {
	u = s + '~' + t;
	l = n + m + 1;
 
	ord[l] = -1;
	for (int i = 0; i < l; i++) ord[i] = u[i], suff[i] = i;
	auto cmp = [](int A, int B) {
		if (ord[A] == ord[B]) return ord[A + p] < ord[B + p];
		return ord[A] < ord[B];
	};
	while (p <= l) {
		sort(suff, suff + l, cmp);
		nord[suff[0]] = 0;
		for (int i = 1; i < l; i++) {
			nord[suff[i]] = nord[suff[i - 1]];
			if (cmp(suff[i - 1], suff[i])) nord[suff[i]]++;
		}
		for (int i = 0; i < l; i++) ord[i] = nord[i];
		p <<= 1;
	}
 
	for (int i = 0; i < l; i++) rev[suff[i]] = i;
	for (int i = 0; i < l; i++) {
		if (rev[i]) {
			int j = suff[rev[i] - 1];
			while (u[i + h] == u[j + h]) h++;
			lcp[rev[i]][0] = h;
		}
		h = max(h - 1, 0);
	}
 
	for (int i = n + 1; i < l; i++) topgear.insert(rev[i]);
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i <= l - (1 << j); i++) {
			lcp[i][j] = min(lcp[i][j - 1], lcp[i + (1 << j - 1)][j - 1]);
		}
	}
}
 
int rmq(int l, int r) {
	int level = 31 - __builtin_clz(r - l + 1);
	return min(lcp[l][level], lcp[r - (1 << level) + 1][level]);
}
 
bool check(int len) {
	set<int> good;
	good.insert(n);
	for (int i = n - 1; ~i; i--) {
		set<int>::iterator lb = good.lower_bound(i + len);
		if (lb != good.end() && *lb <= i + match[i]) good.insert(i);
	}
	return !*good.begin();
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> t;
	n = s.size(), m = t.size();
 
	build_suffix_arr();
	for (int i = 0; i < n; i++) {
		set<int>::iterator lb = topgear.lower_bound(rev[i]);
		if (lb != topgear.end()) match[i] = max(match[i], rmq(rev[i] + 1, *lb));
		if (lb != topgear.begin()) {
			lb--;
			match[i] = max(match[i], rmq(*lb + 1, rev[i]));
		}
	}
 
	int l = 0, r = n;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << (l ? l : -1);
	return 0;
}
Fundamentos