Quiz
https://yukicoder.me/problems/no/111
Submit
https://yukicoder.me/submissions/336368
解法
- まず、aから始まる回文の数を考える
- サンプル2の場合
ababababa
- abaは4つ
- ababaは3つ
- abababaは2つ
- ababababaは1つ
- 取れる。
- 一般に1+2+3+...+Nとなりそう
- ここでNは、abaの場合を考えて(L-3) / 2 + 1
- となる。
- L-3 : 残りの長さ
- 2 : 2ずつずらしながら数える
- +1 : 1番最初の分
- 1+2+3+...+Nの和は等差数列の和なので求まる
- これでabaの場合は求まった
- 文字列から最初と最後のaを取り除くと
bababab
- これはL-2として同様に数えられる
- よってO(1)で解くことができました
