Necklace

Solución 1 (DP mágico)

Complejidad temporal: $\mathcal O(N^2)$ . Complejidad de memoria: $\mathcal O(N)$ .

Código


// DP: time O(n^2), mem O(n)
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int solve_noflip(string &s, string &t, int *loc) {
	int n = s.size();  // vertical
	int m = t.size();  // horizontal
	int res = 0;
	vector<short> forw_back_len(m + 1);
	vector<short> cur_v_len(n + m + 1);  // offset -n
	vector<short> cur_v_y(n + m + 1);
	for (int i = 0; i <= n; ++i) cur_v_y[n - i] = i;
	vector<short> cur_h_len(m + 1);
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) forw_back_len[j] = max(0, forw_back_len[j] - 1);
		for (int j = 0; j <= m; ++j) {
			int idx = n - i + j;
			while (cur_v_y[idx] - cur_v_len[idx] == i) {
				int y = cur_v_y[idx];
				// x-j == y-i
				int x = y - i + j;
				forw_back_len[x] = max(forw_back_len[x], cur_v_len[idx]);
				if (y == n || x == m) {
					cur_v_y[idx] = -1;
				} else {
					++cur_v_y[idx];
					if (s[y] == t[x]) {
						++cur_v_len[idx];
					} else {
						cur_v_len[idx] = 0;
					}
				}
			}
		}
		vector<short> back_forw_len(m + 1);
		for (int j = 0; j <= m; ++j) {
			int nj = j - cur_h_len[j];
			back_forw_len[nj] = max(back_forw_len[nj], cur_h_len[j]);
		}
		for (int j = 1; j <= m; ++j) {
			back_forw_len[j] = max((int)back_forw_len[j], back_forw_len[j - 1] - 1);
		}
		for (int j = 0; j <= m; ++j) {
			if (forw_back_len[j] + back_forw_len[j] > res) {
				res = forw_back_len[j] + back_forw_len[j];
				loc[0] = i - back_forw_len[j];
				loc[1] = j - forw_back_len[j];
			}
		}
		if (i < n) {
			for (int j = m - 1; j >= 0; --j) {
				if (s[i] == t[j]) {
					cur_h_len[j + 1] = cur_h_len[j] + 1;
				} else {
					cur_h_len[j + 1] = 0;
				}
			}
			cur_h_len[0] = 0;
		}
	}
	return res;
}
 
int solve(string &s, string &t, int *loc) {
	int loc_noflip[2];
	int res = solve_noflip(s, t, loc_noflip);
	reverse(t.begin(), t.end());
	int loc_flip[2];
	int res_flip = solve_noflip(s, t, loc_flip);
	if (res_flip > res) {
		res = res_flip;
		loc[0] = loc_flip[0];
		loc[1] = (int)t.size() - loc_flip[1] - res;
	} else {
		for (int i = 0; i < 2; ++i) loc[i] = loc_noflip[i];
	}
	return res;
}
 
int main() {
	cin.sync_with_stdio(false);
	string s, t;
	cin >> s >> t;
	int loc[2];
	int res = solve(s, t, loc);
	cout << res << '\n';
	if (res) { cout << loc[0] << ' ' << loc[1] << '\n'; }
	return 0;
}

Solución 2 (KMP)

Complejidad temporal: $\mathcal O(N^2)$ . Complejidad de memoria: $\mathcal O(N)$ .

Sean las dos cadenas $S$ y $T$ , y sus longitudes $N$ y $M$ respectivamente.

Por simplicidad, supongamos que no podemos dar vuelta el collar. (Para manejar el caso en el que sí podemos, simplemente invertimos $T$ , corremos el algoritmo de nuevo y nos quedamos con el mejor resultado.)

Esencialmente queremos hallar dos cadenas $A$ y $B$ , y dos índices $i$ y $j$ tales que:

$A$ es un sufijo de $S[0 : i]$ y un prefijo de $T[j + 1 : M - 1]$ .
$B$ es un prefijo de $S[i + 1 : N - 1]$ y un sufijo de $T[0 : j]$ .
$|A| + |B|$ es maximal.

Así podemos probar cada $i$ para hallar el mejor $j$ para ese $i$ , y luego tomar el mejor resultado global.

Para hallar el mejor $j$ , primero invertimos $T$ y partimos $S$ en el índice $i$ . Esto convierte el subproblema en hallar el prefijo/sufijo común más largo entre dos pares de cadenas. Esta es una aplicación clásica de KMP, así que podemos resolver este subproblema en tiempo $\mathcal O(N)$ y memoria $\mathcal O(N)$ .

Código


#include <bits/stdc++.h>
using namespace std;
vector<int> pi(const string &s) {
	int n = (int)s.size();
	vector<int> pi_s(n);
	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[j] != s[i]) { j = pi_s[j - 1]; }
		if (s[i] == s[j]) { j++; }
		pi_s[i] = j;
	}
	return pi_s;
}
vector<int> calc(const string &s, const string &t) {
	vector<int> ret(s.size());
	string cur = t + "#" + s;
	vector<int> p = pi(cur);
	for (int i = 0; i < (int)s.size(); i++) ret[i] = p[i + t.size() + 1];
	return ret;
}
pair<int, pair<int, int>> solve(string s, string t) {
	t += ".";
	string s_rev = s;
	reverse(s_rev.begin(), s_rev.end());
	pair<int, pair<int, int>> ans = {0, {0, 0}};
	for (int i = 0; i < (int)t.size() - 1; i++) {
		string t_rev = t;
		reverse(t_rev.begin(), t_rev.end());
		vector<int> left = calc(s, t);
		vector<int> right = calc(s_rev, t_rev);
		reverse(right.begin(), right.end());
		for (int j = 0; j <= (int)s.size(); j++) {
			int l = j == 0 ? 0 : left[j - 1];
			int r = j == (int)s.size() ? 0 : right[j];
			ans =
			    max(ans,
			        {l + r,
			         {j - l, (int)(2 * (t.size() - 1) - r + i) % (int)(t.size() - 1)}});
		}
		rotate(t.begin(), t.begin() + 1, t.end());
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s, t;
	cin >> s >> t;
	pair<int, pair<int, int>> ans = solve(s, t);
	reverse(t.begin(), t.end());
	pair<int, pair<int, int>> cur = solve(s, t);
	cur.second.second = (int)t.size() - cur.second.second - cur.first;
	ans = max(ans, cur);
	cout << ans.first << "\n";
	if (ans.first) cout << ans.second.first << " " << ans.second.second << "\n";
}