回文串的问题我们说一个字符串是回文串,那么意味着这个串从两边读起来的字母都是一样的.例如racecar是回文串,然而fastcar则不是.对一个串的划分意思是将一个串划分为若干个部分.例如,racec
来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/25 14:47:26
回文串的问题我们说一个字符串是回文串,那么意味着这个串从两边读起来的字母都是一样的.例如racecar是回文串,然而fastcar则不是.对一个串的划分意思是将一个串划分为若干个部分.例如,racec
回文串的问题
我们说一个字符串是回文串,那么意味着这个串从两边读起来的字母都是一样的.例如racecar是回文串,
然而fastcar则不是.
对一个串的划分意思是将一个串划分为若干个部分.例如,racecar可以划分为race 和car两部分.给出
一个串,要把这个串划分为若干个回文串,那么至少要把这个串划分为多少部分?
例如
'racecar'已经是回文串,划分为1 个部分即可(这个部分就是racecar).
'fastcar' 需要被划分为七个部分 ('f','a','s','t','c','a','r').根据回文串的定义,单个字母也是回文串.
'aaadbccb' 分成可以被分为三个回文串 ('aaa','d','bccb').找不到更少的划分方法.
Input
输入的第一行是数字T,表示输入文件含有T个CASE.之后有T行,每行有一个长度不大于1000的字
符串,全部由小写字母组成,中间没有空格.
Output
对于每个CASE,输出一个数字,表示对该字符串的回文串最小划分.
回文串的问题我们说一个字符串是回文串,那么意味着这个串从两边读起来的字母都是一样的.例如racecar是回文串,然而fastcar则不是.对一个串的划分意思是将一个串划分为若干个部分.例如,racec
对input部分:
input可以用char 类型的二维数组存储.这里可以用new操作符申请空间,因为输入的T未知.
对程序整体部分:
定义函数cal_num(char * case, int start, int end)来求解每行的回文数的大小,这样主程序只需要调用cal_num(char * case, 0, case长度-1),看起来会比较清楚.
定义函数jdg_huiwen(char * huiwen, int start, int end)来判断一个字符数组是不是回文数.判断的一种思路是将字符数组倒序,将倒序的数组与原序列的数组比较,如果相同,返回true表示是回文数,否则返回false.为了下文判断需要,如果start