Background

Yuzu fans, that is enough.

~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)

Problem Description

Little $\delta$ likes to make up words. He learned a way to make up words.

First, he has a "template string", denoted as $s$. Then he chooses a pair $1 \le l \le r \le |s|$, deletes the $l$-th to $r$-th characters of $s$, and concatenates the remaining parts. He denotes the new string obtained as $s'$.

Next, he chooses a new pair $1 \le l' \le r' \le |s'|$, and lets $s''$ be the string formed by the $l'$-th to $r'$-th characters of $s'$. The word he makes is $s''$.

For example, if the "template string" is $s=\texttt{cciaohalloo}$, then one way is to choose $l=5$, $r=7$, obtaining $s'=\texttt{ccialloo}$, then choose $l'=2$, $r'=7$, obtaining $s''=\texttt{ciallo}$.

Now little $\delta$ has a "target string" $t$. He wants to know how many different plans can use the "template string" $s$ to produce the word $t$. Two plans are defined to be the same if and only if the chosen $l,r,l',r'$ are all the same.

Input Format

There are two lines, which are the strings $s$ and $t$, respectively.

Output Format

There is one line, representing the number of plans to produce the "target string" $t$.

aabbaaba
aba

23

ciaohallo
ciallo

2

babacbbaababbacbababbabbbaaabaabababbabbabababba
ababab

1535

sssssssssssssssssssssssssssssssssssss
sss

15470

abcbbbcbcbcbacbacbaaabcbcbcbaabacbca
cb

3995

Hint

Constraints

This problem uses bundled testdata.

• Subtask 0 (6 points): $|s| \le 400$, $|t| \le 200$.
• Subtask 1 (10 points): $|s| \le 700$, $|t| \le 300$.
• Subtask 2 (10 points): $\forall i,j,s_i=t_j$.
• Subtask 3 (10 points): $|t|=1$.
• Subtask 4 (20 points): $|s| \le 10^4$, $|t| \le 3 \times 10^3$.
• Subtask 5 (14 points): $|t|=2$.
• Subtask 6 (30 points): No special constraints.

For all testdata, $1 \le |s| \le 4 \times 10^5$, $1 \le |t| \le 2 \times 10^5$. $s,t$ contain only lowercase English letters.

Translated by ChatGPT 5