Common Palindromes

時間制限 : 2 sec, メモリ制限 : 65536 KB

C: Common Palindromes

ICPC で良い成績を収めるには修行が欠かせない.うさぎは ICPC で勝ちたいので,今日も修行をすることにした.

今日の修行は,文字列中にある回文を探すことによって,文章から隠れたメッセージを読解する能力を高めようというものである.回文はたくさんあるかもしれないので,探すついでに個数も数えてしまいたい.

2 つの文字列 S, T が与えられるので,以下を満たす整数の組 (i, j, k, l) の個数を求めたい.

  • 1 ≤ ij ≤ (S の長さ).
  • 1 ≤ kl ≤ (T の長さ).
  • Si 文字目から j 文字目までを取り出した部分文字列は,Tk 文字目から l 文字目までを取り出した部分文字列と同一であり,さらにこれらは回文 (左から読んでも右から読んでも同じになる文字列) となっている.

Input

S
T

文字列 S, T はともに長さが 1 以上 50,000 以下であり,アルファベット大文字からなる.

Output

条件を満たす整数の組 (i, j, k, l) の個数を 1 行に出力せよ.

Sample Input 1

ICPC
CPCPC

Sample Output 1

10

Sample Input 2

BABBAB
ABBA

Sample Output 2

14

Sample Input 3

MYON
USAGI

Sample Output 3

0

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011 , Day 2, Tokyo, Japan, 2011-09-18
http://acm-icpc.aitea.net/