5. 最长回文子串

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

s0：暴力解法

列举所有子串，判断是否为回文

 1 class Solution {
 2     bool isPalindromic(string str)
 3     {
 4         for(int i = 0; i < str.size() / 2; i++)
 5         {
 6             if(str[i] != str[str.size() - 1 - i])
 7             {
 8                 return false;
 9             }
10         }
11         return true;
12     }
13 public:
14     string longestPalindrome(string s) {
15         string ans = "";
16         int max = 0;
17         int len = s.size();
18         for(int i = 0; i < len; i++)
19         {
20             for(int j = 1; i + j <= len; j++)
21             {
22                 string tmp_str = s.substr(i, j);
23                 if(isPalindromic(tmp_str) && tmp_str.size() > max)
24                 {    
25                     max = tmp_str.size();
26                     ans = tmp_str;
27                 }
28             }
29         }
30         return ans;
31     }
32 };

s1：最长公共子串

1、dp找最长公共字串

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 string longestPubSubStr(string s1, string s2)
 6 {
 7     string ret;
 8     int m = s1.size();
 9     int n = s2.size();
10     int dp[m][n] = {0};
11     fill(dp[0], dp[0] + m * n, 0);
12     
13     for(int i = 0; i < m; i++)
14     {
15         if(s1[i] == s2[0])
16         {
17             dp[i][0] = 1;
18         }
19     }
20     for(int j = 0; j < n; j++)
21     {
22          if(s1[0] == s2[j])
23         {
24             dp[0][j] = 1;
25         }
26     }
27     int maxLen = 0;
28     int maxLenEndCharIndex = 0;
29     for(int i = 1; i < m; i++)
30     {
31         for(int j = 1; j < n; j++)
32         {
33             if(s1[i] == s2[j])
34             {
35                 dp[i][j] = dp[i - 1][j - 1] + 1;
36                 if(dp[i][j] > maxLen)
37                 {
38                     maxLen = dp[i][j];
39                     maxLenEndCharIndex = i;
40                 }
41             }
42         }
43     }
44     
45     
46     ret = s1.substr(maxLenEndCharIndex - maxLen + 1, maxLen);
47     
48     return ret;
49 }
50 
51 int main()
52 {
53     string s1 = "abac";
54     string s2 = "caba";
55     
56     cout << longestPubSubStr(s1, s2) << endl; 
57     
58     return 0;
59 }

这里的空间复杂度可以优化

#include <bits/stdc++.h>

using namespace std;

int longestPubSubStr(string s1, string s2)
{
    int max_len = 0;
    int n = s1.size();
    int dp[n] = {0};
    
    // i 是列数， j 是行数，按列更新 
    for(int i = 0; i < n; i++)
    {
        for(int j = n - 1; j >= 0; j--)
        {
            if((i == 0 || j == 0) && s1[i] == s2[j])
            {
                dp[j] = 1;
                if(dp[j] > max_len) max_len = dp[j];
            }
            else if(s1[i] == s2[j])
            {
                dp[j] = dp[j - 1] + 1;
                if(dp[j] > max_len) max_len = dp[j];
            }
            else
            {
                dp[j] = 0; //这里使用相同的列需要置0 
            }
        }
    }
    
    return max_len;
}

int main()
{
    string s1 = "abacssss";
    string s2 = "cabassss";
    
    cout << longestPubSubStr(s1, s2) << endl; 
    
    return 0;
}

2、判断最长公共字串是否对应

 1 class Solution {
 2     string longestPubSubStr(string s1, string s2)
 3     {
 4         string ret;
 5         int m = s1.size();
 6         int n = s2.size();
 7         cout << m << n << endl;
 8         int dp[m][n] = {0};
 9         fill(dp[0], dp[0] + m * n, 0);
10         int maxLen = 0;
11         int maxLenEndCharIndex = 0;
12         
13         for(int i = 0; i < m; i++)
14         {
15             if(s1[i] == s2[0])
16             {
17                 dp[i][0] = 1;
18                 if(dp[i][0] > maxLen)
19                 {
20                     maxLen = dp[i][0];
21                     maxLenEndCharIndex = i;
22                 }
23             }
24         }
25         for(int j = 0; j < n; j++)
26         {
27             if(s1[0] == s2[j])
28             {
29                 dp[0][j] = 1;
30             }
31         }
32         
33         for(int i = 1; i < m; i++)
34         {
35             for(int j = 1; j < n; j++)
36             {
37                 if(s1[i] == s2[j])
38                 {
39                     dp[i][j] = dp[i - 1][j - 1] + 1;
40                     if(dp[i][j] > maxLen)
41                     {
42                         int beforeI = m - 1 - i;
43                         if(beforeI + dp[i][j] - 1 == j)
44                         {
45                             maxLen = dp[i][j];
46                             maxLenEndCharIndex = i;
47                         }
48                     }
49                 }
50             }
51         }
52 
53         ret = s1.substr(maxLenEndCharIndex - maxLen + 1, maxLen);
54         
55         return ret;
56     }
57 public:
58     string longestPalindrome(string s) {
59         if(s.size() <= 1) return s;
60         string s1 = s;
61         reverse(s.begin(), s.end());
62         return longestPubSubStr(s, s1);
63     }
64 };