问题 1470. -- 欢欢的回文划分

1470: 欢欢的回文划分

时间限制: 1 Sec  内存限制: 512 MB
提交: 10  解决: 5
[提交][状态][讨论版]

题目描述

我曾听见你的弦歌........
欢欢对着屏幕喃呢着........
欢欢看着屏幕上的歌词,想知道能把一首弦歌串最少划分成几个回文串。如
aaaaa 1
abcde 5
abadd 2
弦歌全部由小写字母组成,最长1e6

输入

单组数据,每组一个小写字母串

输出

最少把这个串划分成几个回文串

样例输入

abad

样例输出

2

提示

注意你的算法复杂度,可以参考回文自动机的border理论
回文border介绍 :
https://blog.csdn.net/calabash_boy/article/details/103153100

来源

[提交][状态][讨论版]