P5685 [JSOI2013] Happy JYY

JYY has many, many good friends in JSOI, such as PUPPY, KFC, and PUPPUP. With so many friends, JYY is happy every day. One day, JYY found that how well friends get along is closely related to their names. For example, PUPPY and PUPPUP get along especially well, but their relationship with KFC is just average. After thinking hard for a long time, JYY finally discovered the pattern. Now JYY wants to know how close the relationship is between two friends. Can you help JYY?

Given two strings $A$ and $B$, representing the names of two of JYY's friends. Let $A(i,\,j)$ denote the substring of $A$ formed by the $i$-th letter through the $j$-th letter. Similarly, we define $B(x,\,y)$. JYY found that the closeness of the relationship between two friends is equal to the number of quadruples $(i,\,j,\,x,\,y)$ that satisfy all of the following conditions: 1. $1\leq i\leq j\leq |A|$. 2. $1\leq x\leq y\leq |B|$. 3. $A(i,\,j)=B(x,\,y)$. 4. $A(i,\,j)$ is a palindrome string. Here, $|A|$ denotes the length of string $A$. JYY hopes you can help him compute the closeness of the relationship between these two friends.

The input consists of two lines, each containing a string $A$ and $B$ made up of uppercase letters.

Output one line containing one integer, representing the closeness, i.e., the number of valid quadruples.

Constraints: $1\leq |A|,\,|B|\leq 50000$. Translated by ChatGPT 5