| 第 15 回 日本情報オリンピック 模擬予選 ２ |
|
|
2015年12月12日
kagamiz
|
JOI 君は, 川柳が大好きである. その中でも彼は回文川柳が好きである.
回文川柳とは次の条件を満たす文字列 s である.
ここで, 文字列 t が回文であるというのは, t と t を反転した文字列 t' が一致する場合のことを指す. たとえば, 文字列 "aba", "aa", "xivix", "o" はそれぞれ回文であるが, 文字列 "mudkip", "ax", "yyaa" は回文ではない.
JOI 君は今, 長さが N のある文字列 S を眺めている. JOI 君は, 文字列 S から連続する 2X + Y 文字を取り出したときに, 回文川柳がいくつあるのかが気になった.このとき, 2 つの回文川柳の取り出した位置が異なれば, たとえ同じ回文川柳だとしても異なるものとして数える.
JOI 君のために, 文字列 S から取り出せる回文川柳の個数を数えるプログラムを作成せよ.
入力は 2 行からなる.
1 行目には, 3 つの整数 N ( 3 ≦ N ≦ 1000 ) と X ( 1 ≦ X ≦ 10 ) と Y (1 ≦ Y ≦ 10) が空白区切りで与えられる. ここで, N は 2X + Y 以上であることが保証されている.
2 行目には, 長さ N の英小文字のみからなる文字列 S が与えられる.
1 行に, 文字列 S から取り出せる回文川柳の個数を出力せよ.
| 入力例 1 | 入力例 2 |
|---|---|
5 1 3 joioi |
20 5 6 aaaaaaaaaaaaaaaaaaaa |
| 出力例 1 | 出力例 2 |
1 |
5 |
入力例 1 では, 1 文字目から 5 文字目の文字列 "joioi" が回文川柳になっている. 文字列 "j", "oio", "i" はそれぞれ回文である.
入力例 2 では, 1 文字目から 16 文字目, 2 文字目から 17 文字目, 3 文字目から 18 文字目, 4 文字目から 19 文字目, 5 文字目から 20 文字目がそれぞれ回文川柳となっている. これらはすべて同じ回文川柳 "aaaaaaaaaaaaaaaa" となるが, 取り出す位置が異なるため別のものとして数えていることに注意せよ.
※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．