字符串应用之最长回文串

你的名字 2022-07-12 02:11 193阅读 0赞

以前做过一个方法就是从中间往两头扩展。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;
        }
    };