寻找最长回文部分列的带c实现代码的构想1
依次囊括所有的子串。
例如在字符串abcdefg情况下
依次包罗
第一次a ab abc abcd abcde abcdef abcdefd第b bc bcd bcde bcdef bcdefg如下判断字符串是否为回文：
int main () intflag=1； 字符串s=' a '； //测试字符串if(s.length(==0) { printf ) '字符串为空')； 返回- 1； }for(intm=0； m s.length ()/2； m () if ) s[m]！=s[s.length(-m-1 ) ] ) flag=0； }if(flag==1) printf ) (是)； elseprintf('no )； 返回0； }要查找最长回文子串的完整代码，请执行以下步骤
实际上，一些遍历可以提前结束。 如果[length-1]或[length-2]与当前扫描的字符相连的字符串是回文串，则它一定是最长的，因此可以直接返回。 但是，由于该方法中的串是从头向尾延伸的，因此没有太大差异。 如果字符串从两端向中心延伸，就可以节约时间。
# include iostream # includestringusingnamespacestd； class解决方案{ public : stringlongestpalindrome (strings ) { int leng=s.length )； int flag=1； 字符串RES； //每个检查的子字符串string res1=' '； res1=res1 s[0]； //保存最终结果的for(intI=0； i leng； I ) for(intj=I； j leng； j ) ) { flag=1； RES=s.substr(I，) j - i 1)； //提取子字符串for (intm=0； m res.length ()/2； m () if ) RES[m]！=RES[RES.Length((-m-1 ) ] ) flag=0； //if(flag==1) if ) (res1.length ) () res1.length ) ) { res1=res； } } }返回res1； }； int main () { string s='ac '； //测试字符串string res； 解决方案CL； RES=cl.longestpalindrome(s； cout res endl； 返回0； }这个方法效率很低。 提交时超时了。 时间复杂度达到了o(n^3)
上课开始。 下课后再做。 我先逃跑。
来了
想法2 )想得乱七八糟的垃圾，跳过就可以了() ) )。
串从两端向中间延伸。
其实这个构想是我最初想出来的，但实现的时候没有成功。 现在下课，看看能不能顺利进行。
先分析一下波浪吧。
首先考虑回文部分列的特征。 两个或多个长度的回文子串有一个共同的特征。 首尾文字一定一样。 我们以此为出发点，考虑以下步骤。
从开头开始扫描字符串进行回文子串的判断，在这个过程中持续更新回文子串直到得到最佳解。 具体操作如下。
字符串asgafa时
首先扫描字符a，记录此时的扫描表。 0。 接下来，从末尾查找a。 找到a的时候，把这个时候的位置记下来。 对于该字符串，得到此时的位置为下标5，并对0-5子串进行回文子串检测。 如果是回文部分列的话，直接返还就可以了。 否则，从后向前继续找a，直到最后撞到。 如此一来，它也是三层for循环，差别不大，实际上还是扫描。 为了提高效率，需要寻找更好的检测条件，减少不必要的遍历，这种方法停止遍历的条件有点混乱，只能去除很少一部分特殊字符
串的不必要遍历，我试一试吧，看能不能AC。之后，如果没有得到回文子串，直接返回首字符即可，即把长度为1的回文子串进行单独处理，上述过程寻找的是长度大于等于2的回文子串。
代码如下
#include <iostream>#include <string>using namespace std;class Solution {public: string longestPalindrome(string s) { int len = s.length(); string temps; string res; int suc = 1; int flag; for(int i=0;i<len-1;i++){//头部走到[len-2]就可以停下了 for (int j = len - 1; j > i; j--) { flag = 1; if (s[i] == s[j]) { temps = s.substr(i, j - i + 1); for (int m = 0; m < temps.length() / 2; m++) { if (temps[m] != temps[temps.length() - m - 1]) flag = 0; } if (flag == 0) continue;//继续向前寻找 else { if ((j == (len - 1) || j == (len - 2))&&suc<(j-i+1)) {//找到 return temps; } else { if (suc < (j - i + 1)) { res = temps; suc = j - i + 1; } } } } } } if (suc == 1) { res = res + s[0]; } return res; }};int main() { string s = "p";//测试字符串 string res; Solution cl; res = cl.longestPalindrome(s); cout << res << endl; return 0;}比思路1快了一些。但还是超出了时间限制。这个方法仅仅对一些特殊的字符串速度快，行不通。
菜狗只好去看题解了。
题解有几种方法，包括但不限于中心扩散法、动态规划方法、Manacher算法。以下分别进行分析。
(得，一下午加一晚上就弄一道题，我可真棒）
题解链接：
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-羞涩的雨-chuan-by-leetcode-solution/
动态规划代码：
class Solution {public: string longestPalindrome(string s) { int len = s.length(); int head = 0; int suc = 1; int len2; vector<vector<int>> table(len, vector<int>(len)); for (int i = 0; i < len - 1; i++) { table[i][i] = 1; } for (int j = 0; j < len; j++) { for (int i = 0; i < j; i++) { if ((j - i) == 1) { if (s[i] == s[j]) { table[i][j] = 1; } else table[i][j] = 0; } else { table[i][j] = (!(s[i] ^ s[j])) && (table[i + 1][j - 1]); } if (table[i][j] == 1) { len2 = j - i + 1; if (suc < len2) { suc = len2; head = i; } } } } return s.substr(head, suc); }};