#1032 : 最长回文子串时间限制:1000ms单点时限:1000ms内存限制:64MB描述 小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。 这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？” 小Ho奇怪的问道：“什么叫做最长回文子串呢？” 小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~” 小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？ 小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。”样例输入3abababaaaaabaaacacdas样例输出753解题思路1：截取max大小的子串，判断它是否是回文串，一个个遍历（max为str长度时，就一个子串，即它自身，为str长度减一时就有两个子串，依此类推），直到找到第一个回文串时，它对应的max就是最大回文子串长度。此思路对应于下面的“提示一”，代码在“提示一”下面，在hihoCoder上提交，程序会运行超时。提示一：良久，小Ho仍然没有头绪，于是只能向小Hi求助。小Hi清了清嗓子，缓缓说道：“让我从简单的说起吧，我给你一个字符串，你能不能告诉我它是不是一个回文串呢？”小Ho回答道：“这个我当然可以啦！只要将这个字符串反过来，然后比较和原来的字符串是不是一样的不就行了？”小Hi追问道：“也就是说你想要新建一个字符串咯？”小Ho道：“那是当然，不然怎么比较呢？”小Hi笑道：“但是你有没有注意到你在比较原来的字符串A和新字符串B的时候，A的第一个字符就是B的最后一个字符，而A的最后一个字符就是B的第一个字符，那么这样就比较了两次是不是浪费了效率呢？”小Ho恍然道：“似乎是这样的！我知道了，我也不需要新建一个字符串了，我只需要比较A的第一个字符和最后一个字符是否相同，第二个字符和倒数第二个字符是否相同，以此类推，这样就只要比较字符串长度的一半次数就行了是不是？”小Hi回答道：“没错！那你对于一个字符串，一一枚举它的子串，然后判断这个子串是不是回文子串，如果是的话就更新当前保存的最长的那一个，是不是就可以了？”小Ho开心道：“是的！这个问题是不是就这么解决了？”小Hi叹息道：“NONONO！你这最多也就拿个60分吧。”小Ho遗憾的说道：“才及格啊，那我要怎么多拿点分呢？”代码：#include <iostream>#include <string>using namespace std;/* 判断是否为回文串，是则返回true，不是则返回false */bool isPalindrome(string str){int begin, end;begin = 0;end = str.length() – 1;while (begin <= end){if (str[begin] == str[end]){begin++;end–;}else{return false;}}return true;}int main(){int N, max, len, i;bool findMax;string str, subStr;cin >> N;while (N){N–;cin >> str;max = len = str.length();findMax = false;/* 截取max大小的子串，判断它是否是回文串，一个个遍历（max为str长度时，就一个子串，即它自身，为str长度减一时就有两个子串，依此类推），直到找到第一个回文串时，它对应的max就是最大回文子串长度 */while (!findMax){/* 遍历所有长度为max的子串 */for (i = 0; i + max <= len; i++){subStr = str.substr(i, max);if (isPalindrome(subStr)){findMax = true;break;}}max–;}cout << max + 1 <<endl;}system("pause");return 0;}
风景如何，其实并不重要。重要的是，你在我的身边。
