AT_abc237_h [ABC237Ex] Hakata

题目描述

有一个由小写英文字母组成的字符串 $S$。
每天都在思考回文的高桥博多君，打算从 $S$ 的所有回文子串中选出若干个，告诉小仓乐子小姐。

如果被告知的回文中，存在两个回文，其中一个是另一个的子串，小仓乐子小姐就会生气。

在不让小仓乐子小姐生气的前提下，高桥博多君最多能选出多少个回文？

输入格式

输入为以下格式，从标准输入读取。

$S$

输出格式

请输出答案。

样例 1

输入

ababb

输出

3

样例 2

输入

xyz

输出

3

样例 3

输入

xxxxxxxxxx

输出

1

说明/提示

注释

$S$ 的子串是指从 $S$ 的开头删除 $0$ 个或多个字符、从末尾删除 $0$ 个或多个字符后得到的字符串。
例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

约束条件

• $1 \leq |S| \leq 200$
• $S$ 由小写英文字母组成

样例解释 1

可以选择 aba、bab、bb 这 $3$ 个回文。

样例解释 2

可以选择 x、y、z 这 $3$ 个回文。

由 ChatGPT 4.1 翻译