题目链接：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1010
string S;
int dp[maxn][maxn];
int main()
{
    getline(cin,S);
    int len=S.length();
    int ans=1;
    for(int i=0;i<len;i++)
    {
        dp[i][i]=1;
        if(i<len-1)
        {
        if(S[i]==S[i+1])
            {
                dp[i][i+1]=1;
                ans=2;
            }
        }
    }
    for(int L=3;L<=len;L++)
    {
        for(int i=0;i+L-1<len;i++)
        {
            int j=i+L-1;
            if(S[i]==S[j]&&dp[i+1][j-1])
            {
                dp[i][j]=1;
                ans=L;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


不懂为啥pat过不了gets的编译

getline又不能用char类型的字符数组

 

问题描述
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
方法一：暴力求解
遍历每一个子串，再判断这个子串是不是回文串，最后判断这个串是不是最长的回文子串。
遍历子串的复杂度是O(n^2)，判断是不是回文串的复杂度是O(n)，所以这个算法的复杂度是O(n^3)。
方法二：动态规划法
用一个二维的数组ai来表示从第i位到第j位的子串是不是回文串，在判断从i到j的子串是不是回文串时，可以先看i+1到j-1是不是回文串，再判断i位和j位是不是相同。这个算法中，遍历子串的复杂度仍然是O(n^2)，但是判断是不是回文串的复杂度降到了O(1)，所以这个算法的复杂度是O(n^2)。但是这个算法占据了O(n^2)的空间。
方法三：中心扩展法
顾名思义，任何一个回文串都有一个对称轴，从这个中心的位置开始，向两边扩展，可以得到以此为中心的最长回文串。但是要注意，这个对称轴的位置，可能是一个字符，也可能是两个字符中间。遍历对称轴的位置，复杂度是O(n)，找到以此对称轴为中心的最长回文串，其复杂度是O(n)，所以此算法的复杂度是O(n^2)。这个算法比动态规划好的地方是其空间复杂度只有O(1)。
#include 
#include 
using namespace std;
#define LEN 1000
int main(){
char str[LEN];
cin>>str;
int len=strlen(str);
int maxlen=0,mx;
for(int i=0;i
mx=1;
for(int j=1;(i-j>=0)&&(i+j
if(str[i-j]==str[i+j])
mx+=2;
else break;
}
maxlen=maxlen>mx?maxlen:mx;
}
for(int i=0;i
mx=0;
for(int j=0;(i-j>=0)&&(i+j+1
if(str[i-j]==str[i+j+1])
mx+=2;
else break;
}
maxlen=maxlen>mx?maxlen:mx;
}
cout<
return 0;
}
方法四：manacher算法
预处理
在字符串的开始加上一个'$'符，然后在每个字符中间插上一个'#'。比如，字符串ss='abac'，处理之后是str='$#a#b#a#c#'。接下来的计算针对处理后的字符串。
len数组
然后定义一个len数组，len[i]表示的是以str[i]为中心的最长回文串的半径。
仍以上面的字符为例。str='$#a#b#a#c#'，以str[0]为中心的最长回文串是'$'，其半径是1;以str[4]为中心的最长回文串是'#a#b#a#'，其半径是4;len数组为{1,1,2,1,4,1,2,1,2,1}。可以发现，len[i]-1的值，就是原字符串ss中对应的回文串的长度(以#为中心的是偶长度的回文串，以字符为中心的是奇长度的回文串)。
计算len数组
算法的关键在于在计算len数组时，可以利用前面的结果进行优化。
引入变量maxright表示当前访问到的所有回文子串，所能触及的最右一个字符的位置;同时记录maxright所对应的回文串的对称轴的位置，记为pos。
复杂度分析
考虑p的值的变化，在计算的过程中，p只会增加不会减少，当p增加到strlen(str)时，每个位置的len数组的值都可以立即计算得出。所以算法的复杂度是O(n)。
#include 
#include 
#include 
using namespace std;
#define N 100004
string str,ss;
int len[2*N+1];
int main()
{
cin>>ss;
str="$#";
for(unsigned int i=0;i
{
str+=ss[i];
str+="#";
}
//  cout<
int pos=0,p=0,j=0;
len[0]=1;
for(unsigned int i=1;i
{
j=2*pos-i;
if(p>i)
len[i]=(len[j]>p-i)?(p-i):(len[j]);
else
len[i]=1;
while(i+len[i]=0&&str[i+len[i]]==str[i-len[i]])
len[i]++;
if(i+len[i]>=p)
{
pos=i;
p=i+len[i];
}
}
int ans=0;
for(int i=0;i
{
//      cout<
ans=(len[i]-1>=ans)?len[i]-1:ans;
}
//  cout<
cout<
return 0;
}

	

题目：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1：
输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。
示例2：
输入: "cbbd"输出: "bb"
解题思路：
举个例子，“b”是一个回文子串，左右两边同时加入“a”，则“aba”也一定是回文子串，如此可以得出一个结论：在回文子串左右加入相同的字符，新的子串也一定是回文子串。
长度为1的字符是回文子串。
长度为2的字符串，如果左右字符相同，则该字符串为回文子串。
由1-3的结论可以通过动态规划思想来解此题。
Python代码：
class Solution:    def longestPalindrome(self, s: str) -> str:        s_length = len(s)        # 记录每一个字符片段是否是回文子串        status = [[False] * s_length for _ in range(s_length)]        result = ""        # length是字符串片段的长度        for length in range(s_length):            # i, j 分别指向字符串片段的左右两端            for i in range(s_length):                j = i + length                if j >= s_length:                    break                if length == 0:                    status[i][j] = True                elif length == 1:                    status[i][j] = (s[i] == s[j])                else:                    status[i][j] = status[i + 1][j - 1] and (s[i] == s[j])                if status[i][j] and length + 1 > len(result):                    result = s[i:j + 1]        return result
‍
--END--

	

题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s，知道到字符串中的最长回文子串。假定字符串最大长度为1000. 
分析
这个题目有很多中算法。这里只讲动态规划的算法。 其他的算法可以自己去leetcode上去找。 
动态规划的套路就是你需要先假定你已经找到了答案，然后分析答案的特点。然后给出状态转移方程。只要能够写出递归的状态转移方程，剩下的编码就是小case了。 
假定最长的回文子串已经找到： S[i] S[i+1]...S[j-1]S[j] ，那么一个很明显的规律就是，如果S[i,j] 是回文的话，那么S[i] == S[j] 并且 S[i+1]...S[j-1] 肯定也是回文。 
状态转移方程： 
基本条件：
示例图
代码
public