Zadanie

Bobov tajný koníček je výroba umeleckých diel z rôznych kusov oblečenia. Momentálne sa snaží imitovať svetoznáme maľby. Už sa mu poradilo vyrobiť napodobeninu Gitaristu od Pabla Picassa len pomocou postrihaných nohavíc, podobizeň Mony Lízy od Leonarda da Vinciho pomocou šiltoviek a Van Goghove Slnečnice kombináciou rôznofarebných šálov. Na dalšie umelecké dielo sa rozhodol použiť ponožky.

Bob má v skrini najviac 26 rôznych farieb ponožiek, a tieto farby označíme malými písmenami anglickej abecedy. Ponožky sú v skrini naukladané pekne vedľa seba a hoci to na prvý pohľad môže vyzerať chaoticky, Bob v tom má systém. Aby si Bob svoj systém nepokazil, jediné čo môže pri výrobe umeleckého diela spraviť je vybrať jeden súvislý úsek ponožiek, niektoré z ponižiek použiť na umelecké dielo, zvyšné ponožky popárovať a popárované odložiť do šuflíka. Žiadne ponožky nesmie vrátiť do skrine, žiadne mu nakoniec nemôžu ostať nepoužité a párovať spolu môže samozrejme len ponožky rovnakých farieb.

Bob vie, koľko ponožiek, akých farieb bude potrebovať na svoje umelecké dielo a tiež vie, ako sú naukladané jeho ponožky v skrini. Veľmi by ho zaujímalo, koľkými spôsobmi môže vybrať zo skrine súvislý úsek ponožiek tak, aby mu po odobratí niekoľkých párov ponožiek ostali práve tie ponožky, čo potrebuje na umelecké dielo. Na poradí ponožiek vo vybranom úseku nezáleží.

Úloha

Máme dané dva reťazce písmen \(P\) a \(Q\). Nájdite počet rozdelení \(P\) na \(P_1\), \(P_2\) a \(P_3\), pre ktoré platí:

  • \(P_1\) + \(P_2\) + \(P_3\) = \(P\).
  • Každé písmeno abecedy má v \(P_2\) aspoň toľko výskytov ako v \(Q\).
  • Počet výskytov každého písmena v \(P_2\) má rovnakú paritu ako v počet jeho výskytov v \(Q\).

Formát vstupu

Vstup má dva riadky, na prvom z nich je reťazec \(P\) a na druhom reťazec \(Q\). Oba reťazce sa skladajú z malých písmen anglickej abecedy, ich dĺžka je aspoň 1 a najviac milión. (Samozrejme riešenie, ktoré zvláda len kratšie reťazce dostane čiastkové body.)

Napriek tomu, že časový limit je pomerne voľný, v poslednej sade môžu mať aj riešenia s optimálnou časovou problémy. Ak teda chcete plný počet bodov, odporúčame vyhnúť sa pomalším programovacím jazykom. Časový limit pre všetky vstupy je 1 sekunda, pamäťový limit je 512 megabajtov a horné obmedzenia na dĺžky reťazcov v jednotlivých sadách sú postupne \(100\), \(2\,000\), \(20\,000\), \(100\,000\) a \(1\,000\,000\).

Formát výstupu

Na výstup vypíšte jedno číslo, počet vyhovujúcich úsekov ponožiek v \(P\).

Príklady

Input:

xxxxyy
xx

Output:

6

Input:

abababa
a

Output:

8

Input:

nanananananananabatman
banan

Output:

7

V prvom vstupe, máme tri možnosti ako vybrať xx, jednu možnosť ako vybrať xxxx, xxyy alebo xxxxyy. V druhom sú to štyrikrát a, dvakrát bab a dvakrát ababa. V treťom vstupe sú štyri možnosti, kedy úsek končí b a tri možnosti kedy končí ba.

Písmená reťazca \(P\) postupne označíme \(P[0], P[1], ..., P[n-1]\). Úsek \(P\) od \(\ell\)-tého písmena po \(r\)-té (vrátane) budeme zapisovať \(P[\ell]..P[r]\).

Pre každý prefix \(P\), (teda úsek tvaru \(P[0]..P[r]\)) si spočítame charakteristické číslo, ktoré charakterizuje paritu výskytov jednotlivých písmen. Toto charakteristické číslo bude mať v binárnom zápise na \(i\)-tej pozícii od konca \(0\), ak \(i\)-te písmeno sa v prefixe vyskytuje párny počet krát a \(1\), ak nepárny. Napr. pre reťazec ababebaa budeme mať číslo \(10010_2 = 18\). Keď má abeceda \(26\) písmen, charakteristické číslo je menej ako \(2^{26}\) a zmestí sa do 32 bitovej celočíselnej premennej (napr. int v C++).

Charakteristické číslo pre \(P[0]..P[r]\) označíme \(c_r\). Všetky charakteristické čísla vieme spočítať v lineárnom čase od dĺžky \(P\). Taktiež vieme spočítať charakteristické číslo \(Q\), ktoré označíme \(q\).

 

Odpoveď na úlohu, teda počet rozdelení \(P\) budeme počítať zvlášť pre všetky konce \(P_2\). Spočítať, koľko dobrých \(P_2\) končí \(r\)-tým písmenom \(P\) vieme nasledovne:

Nájdeme najväčšie \(\ell\) také, že \(P[\ell]..P[r]\) má aspoň toľko výskytov každého písmena ako \(Q\). Pokiaľ takéto \(\ell\) neexistuje, pokračujeme ďalším \(r\). Potom odpoveď (počet \(P_2\)) je počet takých \(i\), že \(i\leq \ell\) a zároveň \(P[i]..P[r]\) má rovnakú paritu počtu výskytov písmen ako \(Q\). To je v skutočnosti to isté ako počet \(i\leq \ell\), takých, že počty výskytov písmen \(P[0]..P[i]\) majú rovnakú paritu, ako počty výskytov v \(Q\) mínus počty v \(P[0]..P[r]\). Toto však je počet \(i\leq \ell\) takých, že \(c_i = q\; \mathtt{xor}\; c_r\). To je o dosť ľahší problém, nie?

Ako to však celé robiť efektívne?

Začneme s \(r = 0\) a zvyšujeme \(r\) až dovtedy, kým \(P[0]..P[r]\) nemá z každého písmena aspoň toľko výskytov, čo \(Q\). V takomto prípade vieme, že existuje \(\ell\) a je aspoň \(0\). Nájdeme príslušné \(\ell\). Spočítame počet \(c_i\) rovných \(q\; \mathtt{xor}\; c_r\), takých že \(i\leq \ell\). Zvýšime \(r\) o \(1\), nájdeme \(\ell\), spočítame dobré \(c_i\), zvýšime \(r\) o \(1\), nájdeme \(\ell\), spočítame dobré \(c_i\) a tak ďalej až po koniec. Toto zaberie \(O(n)\) času, plus čas strávený hľadaním \(\ell\)-iek plus čas strávený počítaním dobrých \(c_i\).

Všimnime si, že keď zvýšime \(r\), tak sa \(\ell\) nezníži. Vďaka tomuto poznatku sa dá nachádzať \(\ell\) dosť rýchlo, rozmyslite si ako, tak aby sme pri tom dokopy obetovali najviac \(O(n)\) času. Počas toho celého si budeme vo vhodnej dátovej štruktúre udržiavať pre každú hodnotu \(v\) počet \(c_i\) rovných \(v\). Tieto počty budeme aktualizovať spolu s tým ako rastie \(\ell\), aby sme brali do úvahy len \(i\leq \ell\). Ak je použitá dátová štruktúra vyvažovaný binárny vyhľadávací strom, tak zistiť počet \(c_i\) vieme v čase \(O(\log n)\), ak je dátová štruktúra pole, tak vieme zistiť \(c_i\) v čase \(O(1)\) ale potrebujeme \(O(2^s)\) pamäte, kde \(s\) je počet písmen v abecede.

Potom kompletne celá časová zložitosť je buď \(O(n \log n)\) s \(O(n)\) pamäťovou zložitosťou alebo môžeme mať \(O(n)\) čas a \(O(n + 2^s)\) pamäť. Obe tieto riešenia mohli dostať plný počet bodov. \(n\) je dĺžka reťazca \(P\), (predpokladáme, že \(Q\) je kratšie ako \(P\), inak je odpoveď \(0\)).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.