TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3625
  • 题目
  • P3625划分成回文串
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给一个字符串, 要求把它分割成若干个子串,使得每个子串都是回文串。问最少可以分割成多少个。
    例如:
    “racecar”本身就是回文串,答案为1
    “fastcar”,答案为7,分成的7个回文串为"f", "a", "s", "t", "c", "a", "r"
    “aaadbccb”,答案为3,分成的3个回文串为"aaa", "d", "bccb"

    输入格式

    一行,一个由小写字母构成的字符串,该字符串的长度不超过2000

    输出格式

    一行,一个整数,表示最少分割出的回文串的个数。

    样例输入

    样例输入1:
    racecar

    样例输入2:
    fastcar

    样例输入3:
    aaadbccb

    样例输出

    样例输出1:
    1

    样例输出2:
    7

    样例输出3:
    3


    来源  uva11584