Na izolovanom ostrove v Atlantickom oceáne, na ktorý až donedávna ľudská noha nevkročila, objavili vedci nový druh príbuzný ľudom – homo antisapiens. Výzorom je veľmi podobný človeku, a je dokonca schopný vyslovovania všetkých hlások. Ako sa však ukázalo, ich schopnosť vyjadrovať sa, je pomerne obmedzená.
Rečové centrá tohto druhu sú totiž decentralizované, a na nízkej úrovni – každá hemisféra mozgu si vie zapamätať najviac jedno slovo. Preto má každý jedinec uložené jedno slovo v ľavej a jedno slovo v pravej hemisfére, pričom tieto slová môžu, ale nemusia byť rovnaké.
Keď chce príslušník rodu homo antisapiens vysloviť nejaké slovo, tak povie nejaký začiatok slova ľavej hemisféry a potom nejaký koniec slova pravej hemisféry. Obe časti musia byť dlhé aspoň jeden znak.
Napríklad ak ľavá hemisféra pozná slovo jedlo
a pravá slovo lopta
, tak jedinec vie vysloviť slová ja
, jedlolopta
1, jedlopta
, jepta
, jedllopta
, … ale nevie vysloviť lopta
(lebo by nepoužil nič z jedlo
), ani jedlop
(lebo lop
nie je koniec slova lopta
) a dokonca ani ptajed
(lebo ľavá hemisféra musí povedať svoju polovicu skôr).
Vedci by chceli porozumieť jedincom tohto druhu, nakoľko často robia na prvý pohľad nezmyselné veci (tlačia veľký balvan na vrch hory). Radi by však najprv vedeli, či počet slov vysloviteľný týmto druhom nie je priveľký, aby ich výskum nebol taktiež sizyfovský.
Úloha
Dané sú dva reťazce malých písmen anglickej abecedy – slová \(A, B\). Zistite, koľko existuje rôznych slov \(W\) takých, že nejaká začiatočná časť slova \(W\) je neprázdny prefix \(A\) a zvyšná časť slova \(W\) je neprázdny sufix \(B\).
Formát vstupu
Na prvom riadku vstupu je slovo \(A\), a na druhom slovo \(B\).
Obmedzenia veľkosti vstupov pre jednotlivé sady sú nasledovné:
Sada | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
Maximálna dĺžka slov \(A\), \(B\) | 32 | 425 | 5657 | 75212 | 1000000 | 1000000 |
Navyše, v sade 6 platí pre každé zo slov \(A, B\) nasledovné: rovnaké písmená tvoria v oboch slovách súvislý úsek. (Vo vstupe môže byť napríklad \(aaaxuupkkkkkll\), ale nie \(abaaacccb\).)
Formát výstupu
Na jediný riadok výstupu vypíšte počet vyhovujúcich slov.
Príklad
Input:
aha
haha
Output:
9
(Znakom \(|\) označíme, kde končí prefix a začína sufix.) Všetky možnosti, ako vybrať vhodný prefix a sufix, sú \(a|a, ah|a, aha|a, a|ha, ah|ha, aha|ha, a|aha, ah|aha, aha|aha, a|haha, ah|haha, aha|haha\). Z toho si všimneme, že \(ah|a = a|ha, aha|ha = ah|aha = a|haha\). Z pôvodných 12 máme iba 9 rôznych, teda správny výsledok je 9.
Input:
zeleny
akokrava
Output:
48
Input:
stastnynovyrok
vyrok
Output:
64
Taktiež nazývané melón.↩
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.