Orderly Class

Interview

Time limit2sMemory limit512 MB

Summary

Given two equal-length strings A and B, count the intervals in A such that reversing that interval turns A into B.

Level: Medium6 of 10
Topics: String, Two pointers, Implementation, Brute force
Solved: No attempts yet

Problem

Ms. Thomas is managing her class of $n$ students. She placed all of them in a line and gave the $i$ -th student from the left a card with the letter $a_i$ written on it.

She would now like to rearrange the students so that the $i$ -th student from the left holds a card with the letter $b_i$ written on it. She has one way to do it. She chooses a group of consecutive students and reverses the order of that group. Every student keeps the original card while the group is reversed.

Count the ways to do this. Two ways are different when the first position or the last position of the chosen group differs. If no single reversal turns $A$ into $B$ , the answer is 0.

For $A$ equal to abba and $B$ equal to aabb, the only group is a(bba). For $A$ equal to caxcab and $B$ equal to cacxab, there are two groups, ca(xc)ab and c(axca)b. For $A$ equal to a and $B$ equal to z, there is no group to choose.

Input

The first line holds the string $A$ and the second line holds the string $B$ . Both strings consist of lowercase English letters only. The $i$ -th character of $A$ is $a_i$ and the $i$ -th character of $B$ is $b_i$ . The two strings have the same length $n$ with $1 \le n \le 100000$ , and $A$ and $B$ are not identical.

Output

Print one integer, the number of ways to reverse a single consecutive group of $A$ so that the result is $B$ .

Examples3

Example 1
Input
```
abba
aabb
```
Expected output
```
1
```
Example 2
Input
```
caxcab
cacxab
```
Expected output
```
2
```
Example 3
Input
```
a
z
```
Expected output
```
0
```