
ZOJ Problem Set  4110
BaoBao has just found two strings $s = s_1s_2\dots s_n$ and $t = t_1t_2\dots t_n$ in his left pocket, where $s_i$ indicates the $i$th character in string $s$, and $t_i$ indicates the $i$th character in string $t$. As BaoBao is bored, he decides to select a substring of $s$ and reverse it. Formally speaking, he can select two integers $l$ and $r$ such that $1 \le l \le r \le n$ and change the string to $s_1s_2\dots s_{l1}s_rs_{r1} \dots s_{l+1}s_ls_{r+1}\dots s_{n1}s_n$. In how many ways can BaoBao change $s$ to $t$ using the above operation exactly once? Let $(a, b)$ be an operation which reverses the substring $s_as_{a+1} \dots s_b$, and $(c, d)$ be an operation which reverses the substring $s_cs_{c+1} \dots s_d$. These two operations are considered different, if $a \ne c$ or $b \ne d$. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains a string $s$ ($1 \le s \le 2 \times 10^6$), while the second line contains another string $t$ ($t = s$). Both strings are composed of lowercased English letters. It's guaranteed that the sum of $s$ of all test cases will not exceed $2 \times 10^7$. OutputFor each test case output one line containing one integer, indicating the answer. Sample Input2 abcbcdcbd abcdcbcbd abc abc Sample Output3 3 HintFor the first sample test case, BaoBao can do one of the following three operations: (2, 8), (3, 7) or (4, 6). For the second sample test case, BaoBao can do one of the following three operations: (1, 1), (2, 2) or (3, 3). Author: WENG, Caizhi Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 