Podział słowa jest palindromiczny, jeśli kawałki tworzące podział same tworzą palindrom. Np. dla słowa abbcdbab palindromicznym jest podział ab|b|cd|b|ab, bo

i

-ty od przodu i

i

-ty kawałek od tyłu są takie same.

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 $d p [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ę:

$d p [i] = max_{j > i} (2 + d p [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 p o d z (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 p o d z (s_{1}) \cdot (v_{1} \cdot v_{2})^{k} \cdot v_{1} .$