經(jīng)典求最長回文子串問題 可以 - 暴力(O(N^3)) - DP(O(N^2)) 不過本文采用 Manacher’s Algorithm 具體參考 https://www.felix021.com/blog/read.php?2040 寫得非常好,非常好理解,我就不復(fù)述了,實際上很多字符串處理算法的核心就是用了之前計算過的結(jié)果,構(gòu)造一個不等式來減少計算量
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; }};新聞熱點
疑難解答
