Necklace

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$.

Rozwiązanie sześcienne

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);
}

Rozwiązanie kwadratowe

Spróbujemy szybciej wyznaczać wartości $le{n}_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^{\prime }$ słowa $s_2$. Ponieważ wiemy, że mamy równość fragmentów $s_1[i..i+\ell )=s_2[j^{\prime }..j^{\prime }+\ell )$, dla $\ell =lcp[i][j^{\prime }]$, to widać, że dla $j=j^{\prime }+1,j^{\prime }+2,\dots ,j^{\prime }+\ell$ mamy $le{n}_b[i][j]\ge j-j^{\prime }$.

Możemy zatem przejść po wszystkich takich fragmentach i utrzymywać najdłuższy „daszek”, który ciągle pokrywa naszą pozycję $j^{\prime }$:

  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ę $le{n}_a$. Ten algorytm będzie działał w czasie $O(n^2)$ i rozwiąże podzadanie 3.

Pamięć liniowa

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 $le{n}_b[i][\cdot ]$.

Po przeorganizowaniu kodu liczącego tablicę $le{n}_a$ (np. odwróceniu obu słów $s_1$ i $s_2$ i uruchomieniu algorytmu jak dla $le{n}_b$), również możemy wyznaczyć jeden wiersz $le{n}_a[i][\cdot ]$.

Dzięki temu odzyskamy odpowiedź dla ustalonej pozycji $i$.