LeetCode 214. 最短回文串（马拉车算法）

柔情只为你懂 2022-12-02 04:26 166阅读 0赞

[https://leetcode-cn.com/problems/shortest-palindrome/][https_leetcode-cn.com_problems_shortest-palindrome]

策略很容易看出来，只要求出以s\[0\]为起点的最长回文子串长度就行，因为以s\[0\]为起点的最长回文子串已经满足了回文串的要求，接下来只需要在前面加上s剩余部分的逆序即可。

即将s分成s1+s2，其中s1为以s\[0\]为起点的最长回文子串。

最后答案就是 s2^ + s (s2^表示s2的逆串)

那么下面难点就是判断s\[0\]-s\[i\]是否能构成回文串。如果令i=0.....n，依次去判断的话，复杂度会答案n^2.明显不符合要求

马拉车算法可以在O（n）时间内计算出最长的回文子串，因此本题使用马拉车可以解决。

想要了解马拉车算法的原理，可以参考下面的博客。

[马拉车算法讲解][Link 1]

class Solution {
    public:
        string shortestPalindrome(string s) {
            string ans;
            if(s.size()==0)
            {
                return ans;
            }
           int mid = Manacher(s);
           int l,r;
           if(mid%2)
           {
               l = 0;
               r = mid/2+mid/2;
           }
           else
           {
               l=0,r=mid/2-1+(mid/2);
           }
           int n = s.size();
          // cout<<mid<<endl;
           //cout<<l<<" "<<r<<endl;
           for(int i=n-1;i>=r;i--)
           {
               ans.push_back(s[i]);
           }
           for(int i=0;i<n;i++)
           {
               ans.push_back(s[i]);
           }
           return ans;
        }
        int Manacher(string s)
        {
            string sNew = "$#";
            for (auto iter = s.cbegin(); iter != s.cend(); iter++)
            {
                sNew += *iter;
                sNew += "#";
            }
    
            int iNewSize = sNew.size();
            int iMaxSubStringLength = -1;    // 最长回文子串的长度
            int iMaxSubStringPos = -1; // 最长回文子串中心点的位置
            vector<int> p(iNewSize, 0);
            int id = 0;
            int mx = 0;
            int ans;
            for (int i = 1; i < iNewSize; i++)
            {
                if (i < mx)
                {
                    p[i] = min(p[2 * id - i], mx - i);
                }
                else
                {
                    p[i] = 1;
                }
    
                while (sNew[i - p[i]] == sNew[i + p[i]])  // 最左边sNew[0]='$',最右边sNew[sNew.size()] = '\0'，无需判断边界
                {
                    p[i]++;
                }
    
                if (mx < i + p[i])  //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率  
                {
                    id = i;
                    mx = i + p[i];
                }
                if(i-p[i]==0)
                {
                    //cout<<i<<" .."<<endl;
                    ans = max(i,ans);
                }
            }
            return ans;
        }
    };

[https_leetcode-cn.com_problems_shortest-palindrome]: https://leetcode-cn.com/problems/shortest-palindrome/
[Link 1]: https://blog.csdn.net/Form_/article/details/79766986