Count Prefix-Suffix Pairs Forming a Target String

Given two strings s and t, count the number of pairs of indices \((i, j)\) (with \(1 \leq i, j \leq n\), where \(n\) is the length of s) such that if you take the suffix of s starting at index \(j\) (i.e. \(s_j s_{j+1} \dots s_n\)) and the prefix of s of length \(i\) (i.e. \(s_1 s_2 \dots s_i\)) and concatenate them (i.e. forming \(yx\)), the resulting string equals t.

Formally, let \(n = |s|\) and \(m = |t|\). You need to count the number of pairs \((i,j)\) such that:

\[ \underbrace{s_{j}s_{j+1}\dots s_{n}}_{\text{suffix}} \;\Vert\; \underbrace{s_{1}s_{2}\dots s_{i}}_{\text{prefix}} = t, \]

with \(1 \le i, j \le n\).

Note: The pair is valid only if the total length satisfies \(i + (n - j + 1) = m\) and the corresponding parts of s exactly match the parts of t as described.

inputFormat

The input consists of two space-separated strings s and t on a single line.

Constraints:

• \(2 \le |t| \le 2|s|\)
• \(1 \le |s| \le 10^5\)

outputFormat

Output a single integer representing the number of valid pairs \((i,j)\) such that the concatenation of \(s[j\ldots n]\) and \(s[1\ldots i]\) equals t.

sample

abcde deabc

1