Синхронне відлуння#13118

Синхронне відлуння

3 секунди

256 мегабайтів

Дано два рядки $s$ і $t$ , що складаються з малих латинських літер.

Для непорожнього рядка $x$ позначимо через $p_{1} < p_{2} < \dots < p_{k}$ p_1<p_2<\ldots<p_k усі позиції початку його входжень у $s$ , а через $q_{1} < q_{2} < \dots < q_{m}$ q_1<q_2<\ldots<q_m — усі позиції початку його входжень у $t$ . Позиції нумеруються з $1$ .

Назвемо рядок $x$ синхронним, якщо $k = m \geq 3$ k=m\ge 3 та існує ціле число $d$ , для якого

q_{i} = p_{i} + d для всіх 1 \leq i \leq k .

q_i=p_i+d\quad\text{для всіх }1\le i\le k.

Інакше кажучи, усі входження $x$ в одному рядку можна зсунути на однакову кількість позицій, щоб вони збіглися з усіма його входженнями в іншому рядку. Зсув $d$ може бути додатним, від'ємним або нульовим і може бути різним для різних рядків $x$ .

Знайдіть кількість різних непорожніх синхронних рядків. Два рядки вважаються різними, якщо вони відрізняються довжиною або хоча б одним символом. Входження можуть перекриватися.

Вхідні дані

Перший рядок містить рядок $s$ , другий — рядок $t$ ( $1 \leq ∣ s ∣, ∣ t ∣ \leq 2 \cdot 1 0^{5}$ 1\le |s|,|t|\le 2\cdot 10^5). Обидва рядки складаються лише з малих латинських літер.

Вихідні дані

Виведіть одне ціле число — кількість різних непорожніх синхронних рядків.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі підходять шість рядків: a, b, c, ab, bc, abc. Зокрема, abc входить у $s$ на позиціях $1, 4, 7$ , а в $t$ — на позиціях $2, 5, 8$ , тому для нього $d = 1$ d=1.

У другому прикладі a входить у кожен рядок тричі, але на позиціях $1, 3, 5$ та $1, 2, 4$ . Одним зсувом сумістити ці набори неможливо. Інших рядків із щонайменше трьома входженнями в кожному рядку немає.

У третьому прикладі підходять рядки a, aa та aaa.

Оцінювання

Підзадача $1$ ( $30$ балів): $∣ s ∣, ∣ t ∣ \leq 12$ |s|,|t|\le 12.
Підзадача $2$ ( $40$ балів): $∣ s ∣, ∣ t ∣ \leq 100$ |s|,|t|\le 100.
Підзадача $3$ ( $60$ балів): $∣ s ∣, ∣ t ∣ \leq 2000$ |s|,|t|\le 2000.
Підзадача $4$ ( $70$ балів): $s = t$ s=t.
Підзадача $5$ ( $80$ балів): $min (∣ s ∣, ∣ t ∣) \leq 200$ \min(|s|,|t|)\le 200.
Підзадача $6$ ( $120$ балів): без додаткових обмежень.