実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
英小文字からなる文字列 S があります。
毎日回文のことばかりを考えている高橋博多くんは、S の部分文字列のうち回文となっているものをいくつか選び、小倉楽子さんに教えることにしました。
小倉楽子さんは、教えられた回文のうち 2 つであって、一方が他方の部分文字列になっているようなものが存在すると、怒ります。
小倉楽子さんが怒らないという条件のもとで、高橋博多くんは最大でいくつの回文を選ぶことができますか?
注記
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab
は abc
の部分文字列ですが、ac
は abc
の部分文字列ではありません。
制約
- 1 \leq |S| \leq 200
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ababb
出力例 1
3
aba
、bab
、bb
の 3 つの回文を選ぶことができます。
入力例 2
xyz
出力例 2
3
x
、y
、z
の 3 つの回文を選ぶことができます。
入力例 3
xxxxxxxxxx
出力例 3
1
Score : 600 points
Problem Statement
We have a string S consisting of lowercase English letters.
Bob just thinks about palindromes every day. He decided to choose some of the substrings of S that are palindromes and tell them to Anna.
Anna gets angry if one of the palindromes told by Bob is a substring of another.
How many palindromes can Bob choose while not making Anna angry?
Notes
A substring of S is the result of deleting zero or more characters from the beginning and the end of S.
For example, ab
is a substring of abc
, while ac
is not a substring of abc
.
Constraints
- 1 \leq |S| \leq 200
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
ababb
Sample Output 1
3
Three palindromes aba
, bab
, bb
can be chosen.
Sample Input 2
xyz
Sample Output 2
3
Three palindromes x
, y
, z
can be chosen.
Sample Input 3
xxxxxxxxxx
Sample Output 3
1