Score : $600$ points

问题描述

我们有一个由小写英文字母组成的字符串 $S$。
鲍勃每天都在思考回文串。他决定从 $S$ 的子串中选择一些是回文串的并告诉安娜。

如果鲍勃告诉安娜的一个回文串是另一个回文串的子串，安娜就会生气。

鲍勃在不让安娜生气的情况下可以选择多少个回文串？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:16:34