P9543 [Hubei NOI Qualifier Mock 2023] Diary / diary

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.

The input has two lines. The first line contains a string $S$. The second line contains a string $T$.

One line with one integer, the required answer.

### 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