LeetCode 5. Longest Palindromic Substring

2019-11-09 19:39:39

字体：大中小

来源：转载

供稿：网友

经典求最长回文子串问题可以 - 暴力(O(N^3)) - DP(O(N^2)) 不过本文采用 Manacher’s Algorithm 具体参考 https://www.felix021.com/blog/read.php?2040 写得非常好,非常好理解,我就不复述了,实际上很多字符串处理算法的核心就是用了之前计算过的结果,构造一个不等式来减少计算量

class Solution {public: string longestPalindrome(string s2) { string s = "$#"; for (char ch : s2) s = s + ch + '#'; int n = s.size(); int p[n] = {0}; int mx = 0, id = 0; for (int i = 0; i < n; i++) { p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while (s[i + p[i]] == s[i - p[i]]) p[i]++; if (i + p[i] > mx) { mx = i + p[i]; id = i; } } int maxId = 0; for (int i = 1; i < n; i++) if (p[i] > p[maxId]) maxId = i; string ans; for (int i = maxId - p[maxId] + 1; i <= maxId + p[maxId] - 1; i++) if (s[i] != '#') ans += s[i]; return ans; }};

上一篇：写jbpm4.4执行完成最后一个任务遇到如下问题。

下一篇：51Nod - 1655 找规律 + 构造