【Leetcode】最长回文子串

题目链接:最长回文子串

题意:给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

题解:

1、dp做法。思考一下回文子串的条件，头尾至中间相对应，因此我们用这个来记录状态。

dp[i][j]表示从i到j这个字符串。初始化先把dp[i][i]的状态做标记，因为单个字符也算回文串。

同时处理一下相邻且相同的状态，长度为2的回文子串也是特殊的。

然后从长度为3开始我们做一个状态转移。

dp[i][j] = 1的条件是当 dp[i+1][j-1] = 1(i+1 j-1这个字符串也是回文) 并且s[i] == s[j](首尾相同)

与此同时标记一下i和长度。方便最后截取子串作为返回值。

2、manacher(马拉车算法)。我只在打比赛的时候用过这个鬼算法。。这个时间复杂度只有O（n）

kb大佬的板子给出来大家自己做修改吧。

代码:

 1 class Solution {
 2 public:
 3     int dp[1010][1010] = {0};
 4     string longestPalindrome(string s) {
 5         int len = s.length();
 6         if(len <= 0)    return s;
 7         int start = 0,maxlen = 1;  //起始字符位置，以及长度
 8         
 9         //初始化
10         for(int i = 0; i < len; i++){
11             dp[i][i] = 1; 
12             if(i < len-1 && s[i] == s[i+1]){
13                 dp[i][i+1] = 1;
14                 start = i;
15                 maxlen = 2;
16             }
17         }
18         //长度从3开始
19         for(int pos = 3; pos <= len; pos++){
20             for(int i = 0; i <= len-pos ;i++){
21                 int j = i+pos-1;
22                 if(dp[i+1][j-1] && s[i] == s[j]){
23                     dp[i][j] = 1;
24                     maxlen = pos;
25                     start = i;
26                 }
27             }
28         }
29         
30         string ans = s.substr(start,maxlen);
31         return ans;
32     }
33 };

manacher

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1010;
 4 
 5 
 6 char Ma[maxn*2];
 7 int Mp[maxn*2];
 8 void manacher(string s){
 9     int len = s.length();
10     int l = 0;
11     Ma[l++] = '$';
12     Ma[l++] = '#';
13     for(int i = 0; i < len ;i++){
14         Ma[l++] = s[i];
15         Ma[l++] = '#';
16     }
17     Ma[l] = 0;
18     int mx = 0,id = 0;
19     for(int i = 0; i < l; i++){
20         Mp[i] = mx > i ? min(Mp[2*id-i],mx-i):1;
21         while(Ma[i+Mp[i]] == Ma[i-Mp[i]])    Mp[i]++;
22         if(i + Mp[i] > mx){
23             mx = i + Mp[i];
24             id = i;
25         }
26     }
27 }
28 
29 int main(){
30     string s;
31     cin>>s;
32     manacher(s);
33     int len = s.length();
34     int ans = 0;
35     for(int i = 0; i < 2*len+2; i++){
36         ans = max(ans,Mp[i]-1);
37     }
38     cout<<ans<<endl;
39 
40 
41     return 0;
42 }