Palindromiczny podział

Dane jest $n$-literowe słowo $s[0..n)$, dla którego należy obliczyć palindromiczny podział na największą liczbę kawałków.

Rozwiązanie kwadratowe

Jedno z najprostszych rozwiązań to proste programowanie dynamiczne. Przez $dp[i]$ oznaczamy maksymalną liczbę kawałków w palindromicznym podziale słowa $s[i .. n-i)$ (czyli bez pierwszych $i$ liter i bez ostatnich $i$ liter). Łatwo widać rekurencję:

$$dp[i] = \max_{j > i} (2 + dp[j]),$$ gdzie bierzemy pod uwagę takie wartości $j$, że $s[i .. j) = s[n-j .. n-i)$. Równość możemy sprawdzać brutalnie, wtedy dostaniemy rozwiązanie o złożoności $O(n^3)$:

const int N = 1100000;
int t,n,dp[N];
char s[N];

bool substr_equal(int i1, int i2, int len) {
  REP(i,len) {
    if (s[i1+i] != s[i2+i]) return false;
  }
  return true;
}

int main() {
  scanf("%d",&t);
  REP(test,t) {
    scanf("%s",s);
    n = strlen(s);

    dp[n/2] = n%2;
    for (int i=n/2-1; i>=0; --i) {
      dp[i] = 1;
      for (int j=i+1; j<=n/2; ++j) {
        if (substr_equal(i, n-j, j-i)) {
          dp[i] = max(dp[i], 2 + dp[j]);
        }
      }
    }

    printf("%d\n", dp[0]);
  }
}

Można je przyspieszyć do $O(n^2)$ przez użycie haszowania, dzięki któremu porównywanie słów można zrobić w czasie stałym:

void init_hasz() {
  pot[0] = 1;
  REP(i,n) {
    hasz[i+1] = (hasz[i] + ll(s[i])*pot[i]) % P;
    pot[i+1] = ll(pot[i])*A % P;
  }
}

int get_hasz(int i, int len) {
  return ll(hasz[i+len] + P - hasz[i]) * pot[n-i] % P;
}

bool substr_equal(int i1, int i2, int len) {
  return get_hasz(i1, len) == get_hasz(i2, len);
}

Rozwiązanie liniowe

Zadanie można rozwiązać, używając algorytmu zachłannego: wystarczy obcinać ze słowa jak najkrótsze kawałki palindromiczne (czyli najkrótsze prefiksy równe sufiksom). Jeśli użyjemy haszowania, taki program zadziała w czasie $O(n)$:

    int i=0, cnt=0, found=1;
    while (found) {
      found=0;
      for (int j=i+1; !found && j<=n/2; ++j) {
        if (substr_equal(i, n-j, j-i)) {
          i = j;
          cnt += 2;
          found = 1;
        }
      }
    }

    printf("%d\n", cnt + (i<(n+1)/2));

Dlaczego to rozwiązanie jest poprawne? Załóżmy, że w optymalnym rozwiązaniu skrajnym kawałkiem palindromicznym jest $w$, ale rozwiązanie zachłanne wybiera krótszy kawałek $v$. Pokażemy, że rozwiązanie zachłanne znajdzie nie gorszy podział.

Tak więc mamy równość $s = w \cdot s_1 \cdot w$, ale również $s = v\cdot s_2 \cdot v$. Jeśli więc $v$ jest nie dłuższe niż połowa długości $w$, to słowo $w$ musi zaczynać i kończyć się słowem $v$. Tak więc $w = v \cdot w_1 \cdot v$ i mamy palindromiczny podział $s = v \cdot w_1 \cdot v \cdot podz(s_1) \cdot v \cdot w_1 \cdot v$, który ma więcej kawałków niż optymalny, co daje sprzeczność.

Jeśli $v$ nie jest dłuższe niż połowa długości $w$, to oznacza, że słowo $w$ jest okresowe z okresem $|v|$. Tak więc dla pewnego podziału $v = v_1 v_2$ mamy $w = (v_1 \cdot v_2)^k \cdot v_1$. To znowu daje nam lepszy podział palindromiczny $s = (v_1 \cdot v_2)^k \cdot v_1 \cdot podz(s_1) \cdot (v_1 \cdot v_2)^k \cdot v_1.$