以前做过一个方法就是从中间往两头扩展。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; }};新闻热点
疑难解答
