Tandem Copy

Time limit1sMemory limit2048 MB

Summary

Given strings s and t, the task counts the valid substrings of s, where tandem copies of consecutive nucleotides build the sequences and stored forms have no two equal adjacent letters.

Level: Medium6 of 10
Topics: String, Dynamic programming, String matching
Solved: No attempts yet

Problem

A tandem copy on DNA takes one or more consecutive nucleotides and pastes a copy of them directly after the original. For example, tandem copying ATC in ATCG gives ATCATCG. Another tandem copy on ATCATCG gives ATCATTCG. The following chain starts from ATCG: ATCG $\Rightarrow$ ATCATCG $\Rightarrow$ ATCATTCG $\Rightarrow$ ATATCATTCG $\Rightarrow$ $\cdots$

We say that ATCG produces all these sequences by tandem copy. Choosing a different portion to copy at each step lets ATCG produce different sequences, and with enough steps it can produce infinitely many.

Copying a longer portion costs more. Copying ATC from ATCG costs more than copying the single T in ATCATCG. So the length of each copied portion determines the cost.

A single nucleotide is easy to copy, so the lab stores sequences where no two consecutive nucleotides are equal. For example, ATTTG can be produced from ATG by copying T twice, so the lab stores ATG instead.

Input

The input has two lines. The first line is the source string $s$ , and the second line is the target string $t$ . Each string consists of uppercase letters A to Z, and $1 \le |s|, |t| \le 2 \times 10^4$ .

Output

Print one line containing the number of valid substrings of $s$ .

Examples4

Example 1
Input
```
ACGCG
CCG
```
Expected output
```
9
```
Example 2
Input
```
TATCGC
TTCCG
```
Expected output
```
6
```
Example 3
Input
```
ABCABC
ABC
```
Expected output
```
7
```
Example 4
Input
```
ABCABC
ABCABC
```
Expected output
```
1
```