以前做過一個方法就是從中間往兩頭擴展。manacher算法是對這種算法的優化。
比如字符串是FGFXXAXXFGF，在以A為中心的回文串中，還包含FGF這樣回文串，那么當我們計算右邊的FGF時，可以利用左邊FGF的信息，因為他們是對稱的，這就是Manacher算法的思想。
另外考慮奇數和偶數的不同情況，預先對字符串進行預處理，每隔一個字符插入一個“#”，那么原字符假如是ABA將變成#A#B#A#，原字符是AB將變成#A#B#，不論原來奇偶，都將成為奇數，方便計算。
說明，P[i]表示以s[i]為中心可以向右或者向左擴展的才長度，比如ABA，P[0]=1 P[1]=2 P[2]=1
class Solution {PRivate: void Manacher(string &s, vector<int>&P) { int size = s.size(); P[0] = 1; int id = 0; int mx = 0; for (int i = 1; i < size; ++i) { if (mx > i) { P[i] = min(P[2 * id - i], mx - i); } else { P[i] = 1; } while (i - P[i] > -1) { if (s[i + P[i]] == s[i - P[i]]) P[i]++; else break; } if (mx < i + P[i]) { mx = i + P[i]; id = i; } } }public: string longestPalindrome(string s) { int size = s.size(); string copied("#"); for (int i = 0; i < size; ++i) { copied += s[i]; copied += "#"; } vector<int>P(copied.size()); Manacher(copied, P); int pos = 0; int mx = P[0]; string res; for (int i = 1; i<P.size(); ++i) { if (P[i]>mx) { mx = P[i]; pos = i; } } for (int i = pos-mx+1; i < mx + pos; ++i) { if(copied[i]!='#') res += copied[i]; } return res; }};新聞熱點
疑難解答
