Problem Description

Little M decides to start writing a diary, but she does not want to spend too much time thinking about what to write. So she finds a string $S$ of length $n$. She will choose any prefix $P$ of $S$, and any suffix $Q$ of $S$, then concatenate them in order to get the string $P+Q$ as the diary content. Here, the empty string is also considered a prefix and a suffix of $S$, so $P$ and $Q$ each have $n+1$ choices.

Of course, many strings formed this way are meaningless. More specifically, Little M treats a known string $T$ of length $m$ as important information. Any string that contains this important information as a substring is meaningful; otherwise it is meaningless.

Please compute how many essentially different meaningful strings Little M can write in total. “Essentially different” means that for some meaningful string $A$, even if it can be obtained by multiple ways of choosing the prefix and suffix, it should only be counted once.

Input Format

The input has two lines.

The first line contains a string $S$.

The second line contains a string $T$.

Output Format

One line with one integer, the required answer.

aab
ab

7

mikageandspica
spica

140

见选手目录下的 diary/diary3.in 与 diary/diary3.ans。

见选手目录下的 diary/diary3.in 与 diary/diary3.ans。

见选手目录下的 diary/diary4.in 与 diary/diary4.ans。

见选手目录下的 diary/diary4.in 与 diary/diary4.ans。

见选手目录下的 diary/diary5.in 与 diary/diary5.ans。

见选手目录下的 diary/diary5.in 与 diary/diary5.ans。

Hint

Explanation of Sample 1

For the first sample, all meaningful strings that can be formed are ab, aab, aaab, aaaab, aabaab, aabab, aabb, a total of $7$.

Subtasks

For all testdata, it is guaranteed that $1 \leq |S| \leq 5 \times 10^6$, $1 \leq |T| \leq 2|S|$. The input strings $S$ and $T$ contain only lowercase English letters. Here $|S|$ and $|T|$ denote the lengths of strings $S$ and $T$, respectively.

• A set of hack testdata was added on 2023.8.21.

Translated by ChatGPT 5