7. Kryptosekuritné problémy

Jedného dňa si naša hviezdna celebrita Taylor Swift povedala, že je čas na dovolenku. Zaletí si svojím osobným tryskáčom na výlet do kozmu a oslávi debut svojho nového albumu.

Už pomaly vylietavala zo stratosféry, keď si zrazu všimla, že niečo nie je v poriadku. Na obrazovke palubného počítača svieti veľkým červeným písmom:

Muhaha ahoj Taylor,

konečne sme ťa dostali. Tvoj počítač je v našich rukách a s ním aj všetky
tvoje nevydané pesničky.

Tvoj disk sme zašifrovali neprelomiteľnou šifrou a je len na tebe, ako budeš
ďalej pokračovať. Ako výkupné požadujeme len málo. Tvoj červený šál.

S pozdravom,
Tvoji najväčší fanúšikovia.

Čo bude teraz robiť? Má síce veľký tým kyberšpecialistov, ktorý by túto šifru určite rozlúskli, no komunikácia so Zemou z takejto diaľky nie je úplne najjednoduchšia.

Nezostáva jej teda nič iné, len obrátiť sa na vás. Pomôžte jej zistiť, kde na disku sa mohol nachádzať názov jej nového albumu, nech nemusí svojim kyberšpecialistom posielať celý obsah tohto disku.

Úloha

Dostanete \(2\) reťazce \(T\) a \(P\), reprezentujúce obsah zašifrovaného disku a názov Taylorinho nového albumu. Disk je zašifrovaný substitučnou šifrou, teda každé z písmeniek abecedy sa zmenilo na nejaké iné tak, že sa žiadne \(2\) nezmenili na rovnaké.

Formálne reťazec \(A\) sa mohol zašifrovať na reťazec \(B\) vtedy, ak majú rovnakú dĺžku a existuje permutácia písmeniek, ktorá z reťazca \(A\) spraví reťazec \(B\). Ak napríklad \(A = "abdda"\) a \(B = "ceffc"\), tak vyhovuje permutácia \(a \to c\), \(b \to e\) a \(d \to f\). Ak ale \(A = "abb"\) a \(B = "ccc"\), tak neexistuje vyhovujúca permutácia, lebo sa dve písmená nemôžu zmeniť na rovnaké písmeno.

Taylor by teraz zaujímalo, na koľko súvislých podreťazcov reťazca \(T\) sa mohol zašifrovať reťazec \(P\).

Formát vstupu

Na prvom riadku vstupu je reťazec \(P\) (\(|P| \leq 2 \cdot 10^5\)), meno nevydaného albumu.

Na druhom riadku vstupu sa nachádza reťazec \(T\) (\(|T| \leq 4 \cdot 10^5\)), obsah zašifrovaného disku.

Oba reťazce obsahujú len písmená malej anglickej abecedy.

V jednotlivých sadách platia navyše takéto obmedzenia:

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo, počet súvislých podreťazcov \(T\), ktoré sa mohli zašifrovať na reťazec \(P\).

Príklad

Input:

ab
abcdd

Output:

3

Možné podreťazce sa nachádzajú na indexoch 0, 1 a 2. Pri prvom výskyte stačí použiť identickú permutáciu na zašifrovanie. Pri druhom môžeme použiť permutáciu b -> a, c -> b. A pri tretej permutáciu c -> a, d -> b