22496번 - Common Palindromes 다국어

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

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

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

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

S
T

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

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