問題一覧 > 通常問題

No.263 Common Palindromes Extra

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 192 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : uwiuwi / テスター : antaanta
2 ProblemId : 399 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:21

問題文

かつて、Common Palindromesという、その名の通り$2$個の文字列の共通部分回文のペアの個数を求める問題があった。この問題は当時の参加者たちを大いに苦しめた。 あれから$3$年以上の月日が流れ、CPUの性能も競技プログラマの質も格段に向上した。 Common Palindromesでの最速実行時間は$0.05$秒を切るという。したがって文字列の長さを$10$倍にしてもきっと解けるはずだ。

$2$個の文字列$S, T$が与えられるので、以下の条件をすべて満たす組$(i,j,k,l)$の個数を求めよ。なお、文字列$U$の$x$文字目以降$y$文字目以前の連続部分文字列を$U[x,y]$で表す。

  • $1\le i\le j\le (Sの長さ).$
  • $1\le k\le l\le (Tの長さ).$
  • $S[i,j]=T[k,l].$
  • $S[i,j]$は回文。

入力

$S$
$T$

  • $1\le (Sの長さ)\le 500000$
  • $1\le (Tの長さ)\le 500000$
  • $S, T$は英大文字('A'-'Z')のみからなる
  • 上記の制約から、答えはつねに$10^{18}$以下であることが保証される。
  • ※この問題は原題の公開コードをコピペしてACされないように制約が若干きつめに設定されています!!

出力

組$(i,j,k,l)$の個数を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
AABA
BAAB
出力
9

$(1,1,2,2),(1,1,3,3),(2,2,2,2),(2,2,3,3),(4,4,2,2),(4,4,3,3),(3,3,1,1),(3,3,4,4),(1,2,2,3)$の$9$通りです。

サンプル2
入力
USAGI
MYON
出力
0

もちろん原題のサンプルケースも通ります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。