回文の個数

英小文字からなる文字列 S が与えられます。
S のすべての部分文字列のうち、回文になっているものの個数を数えてください。

入力

S

• 文字列 S（1 ≤ |S| ≤ 100）

出力

S の部分文字列のうち、回文になっているものの個数を出力せよ。

入力例1

aba

出力例1

4

（部分文字列: “a”(1), “b”(1), “a”(1), “aba”(1) → 合計4）

入力例2

aaa

出力例2

6

（”a”(3), “aa”(2), “aaa”(1) → 合計6）

入力例3

abc

出力例3

3

（”a”,”b”,”c” のみ）

ポイント

• 部分文字列を全部調べて「回文かどうか」判定すれば O(N³) で解ける。
• 少し工夫すれば「中心から広げる方法」で O(N²) でも解ける。
• アルゴリズム学習にもつながる良い題材

ケン

ヨワモンのパートナー

ヨワモンのパートナー