1. Longest subroutine: Finds the longest subroutine

Dynamic programming I:

class Solution { public: string longestPalindrome(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n)); string result; For (int delta = 0; delta < n; ++delta) { for (int i = 0; i + delta < n; ++i) { int j = i + delta; if (delta == 0) { dp[i][j] = true; } else if (delta == 1) { dp[i][j] = s[i] == s[j]; } else { dp[i][j] = s[i] == s[j] && dp[i+1][j-1]; If (dp[I][j] &&result.size () < delta + 1) {result = s.substr(I, j + 1); } } } return result; }};Copy the code

Time complexity: O(n^2); Space complexity: O(n^2);

Method two: Palindrome center outward expansion

class Solution { public: string longestPalindrome(string s) { int n = s.size(); int start = 0, end = 0; for (int i = 0; i < n; = expandStr(s, I, I); Auto [l2, r2] = expandStr(s, I, I +1); if (r1 - l1 > end - start) { start = l1; end = r1; } if (r2 - l2 > end - start) { start = l2; end = r2; } } return s.substr(start, end - start + 1); } pair<int, int> expandStr(string s, int left, int right) { int n = s.size(); while(--left >= 0 && ++right <= n) { if (s[left] ! = s[right]) { break; } } return {left + 1, right - 1}; }};Copy the code

Method 3: Manacher algorithm: Fill the string into odd digits

class Solution { public: int expand(const string& s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { --left; ++right; } return (right - left - 2) / 2; } string longestPalindrome(string s) { int start = 0, end = -1; string t = "#"; for (char c: s) { t += c; t += '#'; } t += '#'; s = t; vector<int> arm_len; int right = -1, j = -1; for (int i = 0; i < s.size(); ++i) { int cur_arm_len; If (right >= I) {// i_sym = j * 2 - I; Int min_arm_len = min(arm_len[i_sym], right-i); int min_len = min(arm_len[i_sym], right-i); Cur_arm_len = expand(s, i-min_arm_len, I + min_arm_len); Cur_arm_len = expand(s, I, I); } // push_back(cur_arm_len); if (i + cur_arm_len > right) { j = i; right = i + cur_arm_len; } if (cur_arm_len * 2 + 1 > end - start) { start = i - cur_arm_len; end = i + cur_arm_len; } } string ans; for (int i = start; i <= end; ++i) { if (s[i] ! = '#') { ans += s[i]; } } return ans; }};Copy the code