Zadanie

Alchymisti už dávno vedia ako premeniť hlinu na zlato. Nerobia to, pretože by tým mohli vážne ohroziť svetové zásoby hliny (a v zlate sa zemiaky pestujú dosť ťažko). Preto legendárny alchymista Tomimos z Panopoly (skrátene Tomi) sústredil svoje úsilie na výrobu alchymistického prútika. Keď na stôl vedľa seba poukladáme zrnká zlata a zrnká hliny a mávneme prútikom, každé zrnko zlata sa premení na dve zrnká zlata a každé zrnko hliny sa premení na jedno zrnko zlata a jedno zrnko hliny. Po nejakom počte mávnutí sa prútik pokazí a bude treba zohnať ďalší.

Navyše, keď začneme s nejakou konkrétnou postupnosťou zrniek \(S\) a opakovaným mávaním prútika vyrobíme postupnosť zrniek, ktorej podúsek je \(T\), tak sa ten podúsek premení na nový prútik.

Tomiho teraz trápia otázky, či sa tento proces oplatí, po koľkých mávnutiach prútika sa mu podarí vytvoriť nový prútik, koľko zlata pri tom vyrobí, koľko hliny pri tom stratí a či postupom času mu bude počet prútikov narastať alebo klesať a hlavne, či je celý proces výhodnejší ako premena pomocou kameňa mudrcov.

Pre začiatok zistite, po koľkých mávnutiach vnikne z danej postupnosti zrniek nový alchymistický prútik.

Úloha

Zrnko zlata si označíme \(a\) (aurum) a zrnko hliny \(b\) (bahno). Potom postupnosť zrniek zodpovedá reťazcu znakov \(a,b\). Mávnutiu prútika bude zodpovedať funkcia \(p\) taká, že \(p(S)\) je reťazec písmen, ktorý vznikne z \(S\) nahradením \(a\) za \(aa\) a \(b\) za \(ab\). Napríklad \(p(\text{"abaab"}) = \text{"aaabaaaaab"}\).

\(p^k(S)\) označuje \(k\)-násobné aplikovanie funkcie \(p\) na \(S\). Presnejšie \(p^0(S)=S\) a \(p^k(S) = p^{k-1}(p(S))\). Napríklad \(p^3(\text{"b"}) = \text{"aaaaaaab"}\).

Pre dané \(S\) a \(T\) nájdite najmenšie nezáporné \(k\) také, že \(T\) je podreťazec \(p^k(S)\).

Formát vstupu

Vstup má dva riadky, na prvom je \(S\) a na druhom \(T\). Každý reťazec má dĺžku aspoň \(1\) a najviac \(200\, 000\). Oba obsahujú len písmená \(a\) a \(b\).

Formát výstupu

Vypíšte jedno celé číslo \(k\), udávajúce najmenší možný vyhovujúci počet mávnutí, alebo vypíšte \(-1\), ak žiadne vyhovujúce \(k\) neexistuje.

Príklady

Input:

b
ab

Output:

1

Input:

ababa
bab

Output:

0

Input:

a
b

Output:

-1

Namiesto toho, aby sme hľadali \(T\) v \(p^k(S)\), budeme hľadať \(q^k(T)\) v \(S\), pričom \(q\) bude také zobrazenie, aby sa \(q^k(T)\) nachádzalo v \(S\) práve vtedy, keď \(T\) v \(p^k(S)\). Výhodou tohto prístupu je, že \(q\) bude reťazec skracovať približne na polovicu, čím dosiahneme dobrú časovú zložitosť, zatiaľ čo \(p\) reťazec predlžoval, čo by viedlo k pomalým časovým zložitostiam.

Ukážeme si to na príklade, predstavme si, že vstup je: \(T = \text{"baaaaaaabaa"}\) a \(S = \text{"ababa"}\). Správna odpoveď je 2, lebo \(p^2(\text{"ababa"}) = \text{,,aaaaaaa}baaaaaaabaa\text{aa''}\). Odpoveď však vieme spočítať aj tzv. redukovaním, ktoré bližšie popíšeme nižšie:

“baaaaaaabaa” sa nenachádza v “ababa”, preto redukujeme T.

“baaaba” sa nenachádza v “ababa”, preto redukujeme “baaaba”.

“bab?” sa nachádza v “ababa”, preto je odpoveď 2. “?” je žolík, môže pasovať aj na “a” aj na “b”.

 

Redukcia nejakého slova \(A\) je najkratšie také slovo \(B\), že \(p(B)\) obsahuje \(A\). Napríklad \(p(\text{"baaaba"}) = \text{"abaaaaaaabaa"}\), čo obsahuje “baaaaaaabaa”, preto “baaaba” je redukciou “baaaaaaabaa”. V tomto prípade je to jediná možná redukcia, ale vo všeobecnosti nemusí byť redukcia jednoznačne určená. Napríklad “baba” a “babb” sú dve možné redukcie “baaaba”. Na druhej strane, nie každé slovo musí mať redukciu. Napríklad neexistuje redukcia slov “baab” či “bb”.

Dôležité v tejto úlohe je zamyslieť sa, ako redukcia funguje a skúsiť si ju spraviť ručne na papieri pre nejaké slová. Tak si všimneme, že redukcia sa správa pomerne pekne. Jednoduchým lineárnym prechodom vieme spočítať redukciu nejakého slova, alebo povedať, že žiadna neexistuje. Ak nie je redukcia jednoznačná (to je vtedy, keď za posledným béčkom je nepárny počet áčok), tak vždy je nejednoznačný práve jeden posledný znak, ktorý môžeme označiť ako otáznik, ako sme to videli v príklade. Redukcie slov s otáznikom na konci budu mať zasa (jeden) otáznik na konci. Trocha si treba dať pozor na redukcie samých áčok. Redukcia “aaaaa” je “aa?”, prípadne redukcia “a” je “?”.

Naprogramujeme teda redukujúcu funkciu a úlohu vyriešime tak, že dokola redukujeme vstupné \(T\), až kým sa nebude redukované \(T\) vyskytovať v \(S\) (vtedy vypíšeme potrebný počet redukcií) alebo sa nám redukcia nepodarí (vtedy vypíšeme \(-1\)).

 

Ako zistíme, či sa daný reťazec \(T\) nachádza v \(S\)? Jednoduchým KMP algoritmom. V prípade, že hľadaný text končí znakom “?”, tak hľadáme \(T\) bez posledného znaku v \(S\) bez posledného znaku. Časová zložitosť celého algoritmu je \(O(n \log n)\) kde \(n\) je dĺžka vstupu. Spravíme totiž najviac \(O(\log n)\) redukcií.

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