Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to achieve the longest reply substring of C++". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "how to achieve the longest reply substring of C++" can help you solve the problem.

Longest Palindromic Substring longest reply substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

This question asks us to find the longest reply substring, first of all, what is a palindrome string, that is, a string that is the same as both positive and negative reading, such as "bob", "level", "noon" and so on. Then the longest palindrome substring is the longest palindrome substring in a string. There are five questions about palindromes in LeetCode. Except this one, the other four are Palindrome Number,Validate Palindrome,Palindrome Partitioning,Palindrome Partitioning II. We know that the traditional method of verifying palindromes is to verify whether two palindromes are equal. For the problem of retrieving palindromes, it is necessary to look for palindromes with each character as the center, like spreading on both sides. The time complexity of this algorithm is O (nymn), which can be obtained through OJ. It is necessary to pay attention to the parity case, because the length of the palindrome string can be odd or even, for example, "bob" is an odd-numbered palindrome, "noon" is an even-numbered palindrome, both forms of palindromes have to be searched. For odd-numbered palindromes, we will spread to both sides from the position we traverse to. For even-numbered palindromes, we treat the current position and the next position as the two middle characters of the even-numbered line palindromes. Then search both sides, see the code as follows:

Solution 1:

Class Solution {public: string longestPalindrome (string s) {if (s.size ()

< 2) return s; int n = s.size(), maxLen = 0, start = 0; for (int i = 0; i < n - 1; ++i) { searchPalindrome(s, i, i, start, maxLen); searchPalindrome(s, i, i + 1, start, maxLen); } return s.substr(start, maxLen); } void searchPalindrome(string s, int left, int right, int& start, int& maxLen) { while (left >

= 0 & & right

< s.size() && s[left] == s[right]) { --left; ++right; } if (maxLen < right - left - 1) { start = left + 1; maxLen = right - left - 1; } }}; 我们也可以不使用子函数，直接在一个函数中搞定，我们还是要定义两个变量 start 和 maxLen，分别表示最长回文子串的起点跟长度，在遍历s中的字符的时候，我们首先判断剩余的字符数是否小于等于 maxLen 的一半，是的话表明就算从当前到末尾到子串是半个回文串，那么整个回文串长度最多也就是 maxLen，既然 maxLen 无法再变长了，计算这些就没有意义，直接在当前位置 break 掉就行了。否则就要继续判断，我们用两个变量 left 和 right 分别指向当前位置，然后我们先要做的是向右遍历跳过重复项，这个操作很必要，比如对于 noon，i在第一个o的位置，如果我们以o为最中心往两边扩散，是无法得到长度为4的回文串的，只有先跳过重复，此时left指向第一个o，right指向第二个o，然后再向两边扩散。而对于 bob，i在第一个o的位置时，无法向右跳过重复，此时 left 和 right 同时指向o，再向两边扩散也是正确的，所以可以同时处理奇数和偶数的回文串，之后的操作就是更新 maxLen 和 start 了，跟上面的操作一样，参见代码如下： 解法二： class Solution {public: string longestPalindrome(string s) { if (s.size() < 2) return s; int n = s.size(), maxLen = 0, start = 0; for (int i = 0; i < n;) { if (n - i 0 && s[right + 1] == s[left - 1]) { ++right; --left; } if (maxLen < right - left + 1) { maxLen = right - left + 1; start = left; } } return s.substr(start, maxLen); }}; 此题还可以用动态规划 Dynamic Programming 来解，根 Palindrome Partitioning II 的解法很类似，我们维护一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串，当 i = j 时，只有一个字符，肯定是回文串，如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]，如果i和j不相邻，即 i - j >

When = 2, in addition to judging that s [I] and s [j] are equal, dp [I + 1] [j-1] is a palindrome string if it is true. Through the above analysis, the recursion can be written as follows:

Dp [I, j] = 1 if I = = j

= s [I] = = s [j] if j = I + 1

= s [I] = = s [j] & & dp [I + 1] [j-1] if j > I + 1

There is an interesting phenomenon here is that if I change the two-dimensional array in the following code from int to vector, it will time out, which means that the int-type two-dimensional array accesses the vector of std, so try to use the most primitive data type in the future.

Solution 3:

Class Solution {public: string longestPalindrome (string s) {if (s.empty ()) return ""; int n = s.size (), dp [n] [n] = {0}, left = 0, len = 1; for (int I = 0; I

< n; ++i) { dp[i][i] = 1; for (int j = 0; j < i; ++j) { dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1])); if (dp[j][i] && len < i - j + 1) { len = i - j + 1; left = j; } } } return s.substr(left, len); }}; 最后要来的就是大名鼎鼎的马拉车算法 Manacher"s Algorithm，这个算法的神奇之处在于将时间复杂度提升到了 O(n) 这种逆天的地步，而算法本身也设计的很巧妙，很值得我们掌握，参见我另一篇专门介绍马拉车算法的博客 Manacher"s Algorithm 马拉车算法，代码实现如下： 解法四： class Solution {public: string longestPalindrome(string s) { string t ="$#"; for (int i = 0; i < s.size(); ++i) { t += s[i]; t += "#"; } int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0; for (int i = 1; i < t.size(); ++i) { p[i] = mx >

I? Min (p [2 * id-I], mx-I): 1; while (t [I + p [I]] = t [I-p [I]]) + + p [I]; if (mx < I + p [I]) {mx = I + p [I]; id = I } if (resMx < p [I]) {resMx = p [I]; resId = I;}} return s.substr ((resId-resMx) / 2, resMx-1);}}; that's all for "how C++ achieves the longest palindrome substring". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.