6. Idiomatický slovník vzorové riešenie

6
rummur
deedee
aaaaaaa
kajak
abcxxyycba
mMmMmM

1
1
0
0
0
0

Potrebujeme zistiť, či sa reťazec dá rozdeliť na niekoľko párne dlhých palindrómov. V tomto vzoráku budeme pod “palindróm” myslieť párne dlhý palindróm.

Bruteforce

Spočítajme dvojrozmernú tabuľku, kde pre každú začiatočnú a konečnú pozíciu zistíme, či je daný podreťazec vstupného reťazca palindróm. Pre dvojznakové podreťazce je to ľahké, stačí tie dva znaky porovnať. Dlhší podreťazec je palindróm vtedy, keď sa jeho prvý a posledný znak rovnajú, a všetko medzi nimi je tiež palindróm (zistíme z tabuľky). Tabuľku môžeme vypĺňať napríklad v poradí vzostupne podľa dĺžky podreťazca, alebo zostupne podľa začiatočnej pozície, aby sme vždy čítali len z buniek čo už sme naplnili.

Potom už len treba zistiť, či v reťazci vieme cez palindrómy preskákať zo začiatku na koniec. Keď prídeme na nové miesto, pozrieme sa aké palindrómy tam začínajú a na aké ďalšie miesta vďaka tomu dokážeme skočiť. Zo stringologického pohľadu sa pýtame o každom prefixe vstupného reťazca, či je dobrý (nakrájateľný na palindrómy). Z grafového pohľadu hľadáme či existuje cesta v topologicky zoradenom grafe, ktorého vrcholy sú pozície v reťazci (\(0\) až \(n\)) a hrany sú palindrómy.

Toto riešenie má časovú aj pamäťovú zložitosť \(O(n^2)\).

Trochu lepší bruteforce

Ak máme šťastie a vo vstupe je len málo palindrómových podreťazcov, počítať a pamätať si celú \((n+1)\times (n+1)\) tabuľku je trochu mrhanie. Radšej si pamätajme pre každú pozíciu iba zoznam palindrómov, čo na nej začínajú. Grafovo povedané, namiesto matice susednosti si pamätajme zoznamy susednosti každého vrcholu. Spočítame ich tak, že pre každú možnú stredovú pozíciu rozširujeme palindróm doľava aj doprava, až kým nenarazíme na dva rôzne znaky alebo na kraj vstupu.

Dalo by sa povedať, že toto riešenie má časovú aj pamäťovú zložitosť \(O(n+p)\), kde \(p\) je počet palindrómových podreťazcov. Ale to samozrejme stále môže byť priveľa. Napríklad pre vstup zložený iba z \(n\) áčiek je \(p=O(n^2)\).

Ide to pažravo

V skutočnosti platí, že môžeme vždy pažravo (greedy) spredu reťazca odkrojiť najkratší možný palindrómový prefix. Grafovo povedané, môžeme kľudne skákať po najkratšej hrane a nič si tým nepokazíme, nedostaneme sa do žiadnej slepej uličky. Stringologicky povedané, ak z dobrého reťazca (takého čo sa dá nakrájať na palindrómy) odrežeme najkratší palindrómový prefix, aj ten zvyšok bude dobrý reťazec.

Dokážeme to takto. Ukážeme, že ak existuje akékoľvek riešenie, ktoré by náš greedy algoritmus nevyplodil, tak existuje aj krajšie riešenie, ktoré sa od výstupu nášho algoritmu líši trošku menej. Opakovaním tohto procesu dôjdeme k riešeniu, čo sa od výstupu nášho algoritmu nelíši vôbec.

Poďme na vec. Majme nejaké riešenie (nejaké korektné rozdelenie celého reťazca na palindrómy). Možno už začína \(k\) najkratšími palindrómami (t.j. takými čo by na svojej pozícii vybral aj greedy algoritmus), ale tie nás nezaujímajú. Pozrime sa na prvé miesto, kde sa nezhodnú: najkratší vybrateľný palindróm je \(xx^{-1}\), ale zvolené riešenie si namiesto toho vybralo odrezať nejaký dlhší palindróm \(yy^{-1}\). (Reťazec \(x\) je prvá polovica a \(x^{-1}\) znamená opak \(x\).)

Rozoberme dve možnosti:

• \(y\) je relatívne dlhý (\(|y|\geq 2|x|\)). Keďže \(yy^{-1}\) sa na vstupe prekrýva s \(xx^{-1}\), \(xx^{-1}\) musí byť prefixom \(y\). Zapíšme ho ako \(y = xx^{-1}z\) s nejakým (možno prázdnym) zvyškom \(z\). Tým pádom \(yy^{-1} = xx^{-1}zz^{-1}xx^{-1}\). Super, to sú tri palindrómy. Môžeme z obidvoch koncov \(yy^{-1}\) odrezať \(xx^{-1}\) a text medzi nimi bude tiež palindróm. Riešenie, čo takto dostaneme, už začína na nie \(k\) ale aspoň \(k+1\) najkratších palindrómov. O krok sme sa priblížili ku greedy algoritmu.

• \(y\) je relatívne krátky (\(|x|<|y|<2|x|\)). Rozdeľme \(x\) na dve neprázdne časti \(p, q\) na tom mieste, kde končí \(y\). Nech \(x=pq\) kde \(q\) má \(|y|-|x|\) znakov. Potom \(xx^{-1} = pqq^{-1}p^{-1}\), \(y = pqq^{-1}\), \(yy^{-1} = pqq^{-1}qq^{-1}p^{-1}\). Z polohy na vstupe vieme, že \(xx^{-1}\) je prefixom \(yy^{-1}\), preto (po dosadení) \(pqq^{-1}p^{-1}\) je prefixom \(pqq^{-1}qq^{-1}p^{-1}\), preto (po škrtnutí \(pqq^{-1}\)) \(p^{-1}\) je prefixom \(qq^{-1}p^{-1}\). Tak ho napíšme ako \(qq^{-1}p^{-1} = p^{-1}z\) pre nejaký neprázdny zvyšok \(z\). Lenže tým pádom môžeme dosadiť \(xx^{-1} = pp^{-1}z\), čo je spor s pôvodným predpokladom, že \(xx^{-1}\) je na tomto mieste najkratší vybrateľný palindróm. Takže tento prípad nemôže nastať.

Pre úplnosť, podobne sa dá dokázať, že môžeme odkrojiť úplne ktorýkoľvek palindróm. Je to úplne jedno – žiaden rez nevyrobí z dobrého reťazca zlý. Ale toto v našom riešení nebudeme potrebovať, nám sa hodia krátke palindrómy.

Hashovanie

Plán je jasný: náš program prejde celým vstupom a vždy keď si všimne, že od pozície predošlého rezania po aktuálnu pozíciu je to palindróm, odkrojí ho.

Ako môžeme rýchlo zistiť o ľubovoľnom podreťazci, či je to palindróm? Použijeme hashovanie. Hashovanie sa bežne používa, keď chceme rýchlo testovať rovnosť dvoch podreťazcov, ale test palindromicity je vlastne iba test rovnosti vhodného podreťazca pôvodného vstupu a vhodného podreťazca obráteného vstupu.

Hashovacie funkcie prevádzajú reťazce na čísla a správajú sa pomerne chaoticky. Ak sa dva reťazce rovnajú, samozrejme budú mať aj rovnaký hash. Ak sa nerovnajú, pomerne pravdepodobne budú mať rôzny hash. Takže pri porovnávaní dvoch reťazcov sa oplatí najprv porovnať ich hashe. Ak sú rôzne, ušetrili sme si kopu práce. Ak sú rovnaké, môžeme si dať tú námahu porovnať ich znak po znaku (so šťastím ani netreba).

Vyberme si nejaké pekné prvočíslo \(p\) (napríklad \(10^9+9\)) a nejakú peknú konštantu \(a\) (napríklad \(47\); niektorí machri používajú v každom vstupe iné náhodné číslo). Definujme polynomiálny rolling hash reťazca \(S = c_1c_2\ldots c_n\) ako súčet \(H(S) = (c_1a^1 + c_2a^2 + \ldots + c_na^n) \bmod p\).

Táto definícia má všelijaké pekné vlastnosti. Môžeme si zapamätať nielen finálny výsledok, ale aj medzisúčty pre každý prefix nášho reťazca. Vďaka nim budeme vedieť počítať aj hash ľubovoľného podreťazca: \(H(S[x..y]) = (H(S[0..y]) - H(S[0..x])) / a^x\). Pozor, že odčítanie a delenie tiež robíme modulo \(p\).

Delenie modulo \(p\) sa dá robiť tak, že nájdeme inverzné prvky pomocou modulárneho umocňovania a malej Fermatovej vety. Ale to v tejto úlohe vôbec netreba. Stačí si všimnúť, že nás vždy zaujímajú iba porovnania tvaru \(e / a^f \equiv g / a^h \pmod{p}\), čo sa dá upraviť na \(e \cdot a^h \equiv g \cdot a^f \pmod{p}\), čím sa delenia úplne zbavíme.

Greedy algoritmus s hashovaním má priemernú časovú aj pamäťovú zložitosť \(O(n)\).

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const long long P = 1000000009;

bool run() {
  string S;
  cin >> S;

  int N = S.size();

  vector<long long> expo(N+1);
  vector<long long> hashforw(N+1);
  vector<long long> hashback(N+1);

  expo[0] = 1;
  for (int i = 0; i < N; i++) {
    expo[i + 1] = (expo[i] * 47) % P;
    hashforw[i + 1] = (hashforw[i] + expo[i + 1] * S[i]) % P;
    hashback[i + 1] = (hashback[i] + expo[i + 1] * S[N - 1 - i]) % P;
  }

  int start = 0;
  for (int end = 1; end <= N; end++) {
    if ((end - start) % 2 == 0) {
      int mid = (start + end) / 2;

      // S[start..mid] ==? S[mid..end].reverse()
      // (hashforw[mid] - hashforw[start]) / expo[start] ==? (hashback[N - mid] - hashback[N - end]) / expo[N - end]
      // (hashforw[mid] - hashforw[start]) * expo[N - end] ==? (hashback[N - mid] - hashback[N - end]) * expo[start]

      long long l = ((hashforw[mid] - hashforw[start] + P) % P) * expo[N - end] % P;
      long long r = ((hashback[N - mid] - hashback[N - end] + P) % P) * expo[start] % P;
      bool are_probably_equal = l == r;

      if (are_probably_equal) {
        bool are_really_equal = true;
        for (int i = 0; i < mid - start; i++) {
          if (S[start + i] != S[end - 1 - i]) {
            are_really_equal = false;
            break;
          }
        }
        if (are_really_equal) {
          start = end;
        }
      }
    }
  }

  return start == N;
}

int main() {
  int T;
  cin >> T;

  while (T--) {
    cout << (run() ? "1" : "0") << endl;
  }
}