Mamy dwa słowa $s_1$ i $s_2$ o długościach $n_1$ i $n_2$. Chcemy wybrać z nich jak najdłuższe podsłowa $w_1$ i $w_2$ tak, żeby były „naszyjnikowo równoważne”, czyli żeby $w_2$ mogło powstać przez cykliczny obrót i/lub odwrócenie słowa $w_1$.
Najpierw rozważmy trochę prostszy problem słów „cyklicznie równoważnych”. Wtedy istnieje podział $w_1 = u \cdot v$ oraz $w_2 = v \cdot u$. Możemy rozważyć wszystkie możliwe pozycje kropek w tych podziałach w słowach $s_1$ i $s_2$. Oznaczmy je przez $i$ oraz $j$:
i s_1: ....UUUU|VVV.... j s_2: ..VVV|UUUU......
Teraz osobno rozważymy każdą długość $\ell$ słowa $u$ i dla każdej z nich sprawdzimy równość fragmentów $s_1[i-\ell..i) = s_2[j..j+\ell)$. Analogicznie zrobimy dla słów $v$. Na koniec wybierzemy odpowiedź dającą największą sumę długości.
Złożoność będzie wynosić $O(n^3)$, jeśli będziemy umieli w czasie stałym sprawdzić równość słów. W tym celu można użyć haszowania (co da obliczenia wstępne w czasie $O(n)$), ale ponieważ możemy sobie pozwolić na czas $O(n^2)$, to łatwiej nam będzie obliczyć tablicę $lcp[i][j]$, która oznacza największe $\ell$, że mamy równość $s_1[i..i+\ell) = s_2[j..j+\ell)$. To robimy bardzo prostym programowaniem dynamicznym.
Na koniec powróćmy do problemu „równoważności naszyjnikowej”. Tu przyda nam się techniczna sztuczka: wystarczy jeszcze raz wykonać algorytm równoważności cyklicznej dla słowa $s_1$ oraz odwróconego słowa $s_2$ (trzeba jedynie pamiętać o odpowiednim wzięciu indeksu w odwróconym słowie).
Kod wygląda następująco i zalicza dwa podzadania:
const int N = 3100; char s1[N],s2[N]; int n1,n2; int lcp[N][N]; int ans=0, ai, aj; void solve(bool rev) { for(int i=n1-1; i>=0; --i) { for(int j=n2-1; j>=0; --j) { if (s1[i] == s2[j]) { lcp[i][j] = 1 + lcp[i+1][j+1]; } else { lcp[i][j] = 0; } } } REP(i,n1+1) REP(j,n2+1) { int len_a=0, len_b=0; REP(len,i+1) { if (lcp[i-len][j] >= len) { len_a = len; } } REP(len,j+1) { if (lcp[i][j-len] >= len) { len_b = len; } } if (len_a + len_b > ans) { ans = len_a + len_b; ai = i-len_a; aj = rev ? n2-j-len_a : j-len_b; } } } int main() { scanf("%s%s",s1,s2); n1 = strlen(s1); n2 = strlen(s2); solve(false); reverse(s2,s2+n2); solve(true); printf("%d\n%d %d\n", ans, ai, aj); }
Spróbujemy szybciej wyznaczać wartości $len_b[i][j]$, czyli długość słowa $v$, dla pozycji $i$ oraz $j$. Dla ustalonej pozycji $i$ będziemy przechodzić po wszystkich pozycjach $j'$ słowa $s_2$. Ponieważ wiemy, że mamy równość fragmentów $s_1[i..i+\ell) = s_2[j'..j'+\ell)$, dla $\ell = lcp[i][j']$, to widać, że dla $j=j'+1,j'+2,\ldots,j'+\ell$ mamy $len_b[i][j] \geq j-j'$.
Możemy zatem przejść po wszystkich takich fragmentach i utrzymywać najdłuższy „daszek”, który ciągle pokrywa naszą pozycję $j'$:
REP(i,n1+1) { int idx = -1; REP(j,n2+1) { while (idx == -1 || idx < j && idx + lcp[i][idx] <= j) { idx++; } int len = 0; if (idx + lcp[i][idx] > j) { len = j - idx + 1; } cache_len_b[i][j+1] = len; } } REP(j,n2+1) { int idx = -1; REP(i,n1+1) { while (idx == -1 || idx < i && idx + lcp[idx][j] <= i) { idx++; } int len = 0; if (idx + lcp[idx][j] > i) { len = i - idx + 1; } cache_len_a[i+1][j] = len; } }
Analogicznie wyznaczamy tablicę $len_a$. Ten algorytm będzie działał w czasie $O(n^2)$ i rozwiąże podzadanie 3.
Poprzednie rozwiązanie wymaga pamięci $O(n^2)$, ale można je jeszcze poprawić, aby zużywało tylko $O(n)$ pamięci.
Odpowiadanie na zapytania o $LCP$ można zrealizować haszowaniem w pamięci liniowej.
Iterujemy się po wszystkich wartościach $i$. Dla każdej z nich liczymy w pamięci liniowej wiersz tablicy $len_b[i][\cdot]$.
Po przeorganizowaniu kodu liczącego tablicę $len_a$ (np. odwróceniu obu słów $s_1$ i $s_2$ i uruchomieniu algorytmu jak dla $len_b$), również możemy wyznaczyć jeden wiersz $len_a[i][\cdot]$.
Dzięki temu odzyskamy odpowiedź dla ustalonej pozycji $i$.