Good pairs - MarisaOJ: Marisa Online Judge

Good pairs

Time limit: 1000 ms
Memory limit: 256 MB
Given 2 strings $S, T$ of equal length. Let: $$T_a = T_1T_2...T_i$$ $$T_b = T_{i + 1}T_{i + 2}...T_j$$ $$T_c = T_{j + 1}T_{j + 2}...T_n$$ $$\text{and }|T_a|, |T_b|, |T_c| > 0$$ A pair $i < j$ is called good if $T_a, T_b, T_c$ can be rearranged to form a new string $T' = S$. Count the number of good pairs. ### Input - The first line contains string $S$. - The second line contains string $T$. ### Output - Print the number of good pairs. ### Constraints - $1 \le |S| = |T| \le 5000$. ### Example Input: ``` aaab aaba ``` Output: ``` 2 ```