Common Palindromes

Time limit2sMemory limit512 MB

Summary

Count pairs of intervals, one in S and one in T, whose substrings are equal and palindromic; lengths up to 50,000.

Level: Hard8 of 10
Topics: String, String matching, Hash map, Dynamic programming
Solved: No attempts yet

Problem

Getting good results at ICPC takes constant training. The rabbit wants to win at ICPC, so it trains again today.

Today's training is about finding palindromes in strings, to improve the ability to read hidden messages out of text. There may be many palindromes, so while searching, the rabbit also wants to count them.

Given two strings S and T, find the number of integer tuples (i, j, k, l) satisfying the following.

1 ≤ i ≤ j ≤ (length of S).
1 ≤ k ≤ l ≤ (length of T).
The substring obtained by taking characters i through j of S is identical to the substring obtained by taking characters k through l of T, and these substrings are palindromes (strings that read the same from left to right and from right to left).

Input

S
T

Both strings S and T have length between 1 and 50,000 inclusive, and consist of uppercase English letters.

Output

Print the number of integer tuples (i, j, k, l) satisfying the conditions on one line.

Examples3

Example 1
Input
```
ICPC
CPCPC
```
Expected output
```
10
```
Example 2
Input
```
BABBAB
ABBA
```
Expected output
```
14
```
Example 3
Input
```
MYON
USAGI
```
Expected output
```
0
```