LeetCode-5. 最长回文子串（Manacher）

约定不等于承诺〃 2022-05-26 11:43 176阅读 0赞

### 5. 最长回文子串 ###

[题目描述][Link 1]

--------------------

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

*  [最短回文串][Link 2] [Palindrome Permutation][] [回文对][Link 3] [最长回文子序列][Link 4] [回文子串][Link 5]

--------------------

#include<bits/stdc++.h>
    using namespace std;
    /********************提交代码********************/
    char* longestPalindrome(char* s)
    {
        int i,n=0,len=strlen(s);
        char *str=(char*)malloc((3*len)*sizeof(char));
        int *p=(int*)malloc((3*len)*sizeof(int));
        str[n++]='$';//加入字符串首部的字符串
        for(i=0; s[i]; i++)
        {
            str[n++]='#';
            str[n++]=s[i];
        }
        str[n++]='#';
        str[n]='\0';
        int mx=0,id,pos=0,r=0,val=0;;
        p[0]=0;
        for(i=1; i<n; i++)
        {
            if(mx>i)
                if(p[2*id-i]<mx-i)//p[i]表示i处的回文长度
                    p[i]=p[2*id-i];
                else
                    p[i]=mx-i;
            else//如果i大于mx，则必须重新自己算
                p[i]=1;
            while(str[i-p[i]]==str[i+p[i]])//回文串的半径
                p[i]++;
            if(p[i]+i>mx)//记录目前回文字符串扩展最长的id
            {
                mx=p[i]+i;
                id=i;
            }
            if(p[i]>r)
                r=p[i],pos=i;
        }
        int cnt=0;
        val=(r-1);//最长回文串的长度
        pos/=2;//回文串中心位置
        char *ans=(char*)malloc((val+1)*sizeof(char));
        if(val%2)
            for(i=pos-val/2-1; i<pos+val/2; ++i)
                ans[cnt++]=s[i];
        else
            for(i=pos-val/2; i<pos+val/2; ++i)
                ans[cnt++]=s[i];
        ans[cnt]='\0';//不加结束符在OJ上会有多余输出
        return ans;
    }
    /***************************************************/
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        char s[1000];
        while(cin.getline(s,1000))
        {
            cout<<"/"<<longestPalindrome(s)<<"/"<<endl;
        }
        return 0;
    }

最惨的是因为ans结尾没加**\\0**在OJ上结尾会有多余输出卡了好久……┭┮﹏┭┮

[Manacher-求最长回文字符串][Manacher-]基本就是这个代码改的，On的复杂度。

输出是截取字符串起始位置是：**中心点坐标-最大长度/2**。

[Link 1]: https://leetcode-cn.com/problems/longest-palindromic-substring/description/
[Link 2]: https://leetcode-cn.com/problems/shortest-palindrome
[Palindrome Permutation]: https://leetcode-cn.com/problems/palindrome-permutation
[Link 3]: https://leetcode-cn.com/problems/palindrome-pairs
[Link 4]: https://leetcode-cn.com/problems/longest-palindromic-subsequence
[Link 5]: https://leetcode-cn.com/problems/palindromic-substrings
[Manacher-]: https://blog.csdn.net/mikasa3/article/details/47356375