7. Olympiáda vo vyhľadávaní v texte

V Absurdistane sa tento rok koná historicky prvý ročník Olympiády vo vyhľadávaní v texte. Súťaže sa zúčastňujú trojčlenné tímy, a koná sa niekoľko zápasov – v každom zápase proti sebe nastúpia dva tímy. Porazený tím súťaž opúšťa.

Každý zápas má nasledovnú formu:

• Každý tím ukáže protivníkovi zdrojový kód programu, ktorým bude vyhľadávať v texte.

• Oba tímy si tajne vyberú text, v ktorom bude ich súper vyhľadávať. Tiež zvolia slovo, ktoré chcú, aby ich súper našiel v texte. Samozrejme, je nejaké obmedzenie na veľkosť vstupu.

• Spustia sa programy oboch tímov na vstupe, ktorý zadal protivník. Úlohou programov je nájsť všetky výskyty zadaného slova v zadanom texte. Vyhráva rýchlejší z programov.

Knuth, Morris a Pratt sa tiež zaregistrovali na súťaž so svojím algoritmom. Práve začal ich prvý zápas, a ich súperom je niekto, kto je tak naivný, že do súťaže prišiel s naivným algoritmom na vyhľadávanie v texte:

text[1..n] // text dlzky n, v ktorom vyhladavame
slovo[1..m] // slovo dlzky m, ktore hladame v texte
counter = 0

// postupne skusime kazdu poziciu textu ako zaciatok slova
for i = 1 to n:
  // zlava doprava overime, ci sa tam nachadza slovo
  for j = 1 to m:
    if i + j - 1 > n:
      break
    counter += 1
    if text[i + j - 1] != slovo[j]:
      // lisi sa v j-tom znaku, slovo urcite nezacina na pozicii i v texte
      break
    if j == m:
      // nasli sme vyskyt slova v texte, podame o tom oznam a pokracujeme dalej vo vyhladavani

Chcú protivníka totálne zničiť. Vymysleli niekoľko rôznych vstupov, no teraz sa nevedia zhodnúť, ktorý z nich by mali dať protivníkovi. Pomôžte im zistiť, ktorý vstup bude pre protivníka najhorší.

Úloha

Zadaný je text, v ktorom vyhľadávame, a hľadané slovo. Zistite, koľko porovnaní spraví na tomto vstupe naivný algoritmus. (Zaujíma nás teda hodnota premennej counter po skončení algoritmu.)

Formát vstupu

Na prvom riadku vstupu je text, v ktorom vyhľadávame. Na druhom riadku je hľadané slovo. Obe slová obsahujú iba malé písmená anglickej abecedy, a majú dĺžku aspoň \(1\) a najviac \(1\,000\,000\) znakov.

Formát výstupu

Na jediný riadok výstupu vypíšte jedno číslo – počet porovnaní, ktoré spraví naivný algoritmus na vstupe. Toto číslo môže byť veľké, a nemusí sa zmestiť do \(32\)-bitovej premennej (int v c++), odporúčame preto použiť \(64\)-bitové premenné (long long).

Príklady

Input:

aaaa
aab

Output:

9