CY-Left

LeetCode基本功底

5 Longest Palindromic Substring 最长回文子串

5 Longest Palindromic Substring 最长回文子串

原文&翻译

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给出字符串 s, 在 s 中寻找最长对称子串. s 长度限制在 1000 以内

示例:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"

暴力 O(n^2)

以此判断左右是否相等即可, 注意 aa 和 bab 即可

#include <iostream>
#include <string>

using namespace std;

class Solution
{
public:
    string longestPalindrome(string s)
    {
        int len = s.size();
        //if(len == 0) {return false;}
        int start = 0;
        int ended = 0;
        int maxLen = 1;
        for (int i=0; i<len; i++)
        {
            //cout<<s[i]<<endl;
            int curMaxLen = 1;
            int prei = i;
            int nexi = i;
            while (1)
            {
                --prei;
                ++nexi;
                if (prei < 0 || nexi >= len)
                {
                    ++prei;
                    --nexi;
                    break;
                }
                else if(s[prei] == s[nexi])
                {
                    curMaxLen+=2;
                }
                else
                {
                    ++prei;
                    --nexi;
                    break;
                }
            }
            //cout<<i<<' '<<curMaxLen<<' '<<endl;
            if(curMaxLen > maxLen)
            {
                start = prei;
                ended = nexi;
                maxLen = curMaxLen;
                //cout<<'|'<<start<<' '<<ended<<' '<<curMaxLen<<endl;
            }
        }
        //cout<<endl;
        for (int i=0; i<len; i++)
        {
            int curMaxLen = 0;
            int prei = i;
            int nexi = i+1;
            while (1)
            {
                if (prei < 0 || nexi>=len)
                {
                    ++prei;
                    --nexi;
                    break;
                }
                else if(s[prei] == s[nexi])
                {
                    curMaxLen+=2;
                    --prei;
                    ++nexi;
                }
                else
                {
                    ++prei;
                    --nexi;
                    break;
                }
            }
            //cout<<i<<' '<<curMaxLen<<' '<<endl;
            if(curMaxLen > maxLen)
            {
                start = prei;
                ended = nexi;
                maxLen = curMaxLen;
            }
        }
        string firstname(s.substr(start, maxLen));

        return firstname;
    }


};

int main()
{
    Solution a;
    string x = a.longestPalindrome("cbbd");
    cout<<'|'<<endl;
    cout<<x<<'|';
    return 0;
}

搬运过来的

class Solution {
public:
    string longestPalindrome(string s) 
    {
        string T;// Transform S to T
        for(int i=0;i<s.size();i++)
            T+="#"+s.substr(i,1);
        T.push_back('#');

        vector<int> P(T.size(),0); // Array to record longest palindrome
        int center=0,boundary=0,maxLen=0,resCenter=0;
        for(int i=1;i<T.size()-1;i++) {
            int iMirror=2*center-i; // calc mirror i = center-(i-center)
            P[i]=(boundary>i)?min(boundary-i,P[iMirror]):0; // shortcut
            while(i-1-P[i]>=0&&i+1+P[i]<=T.size()-1&&T[i+1+P[i]] == T[i-1-P[i]]) // Attempt to expand palindrome centered at i
                P[i]++;
            if(i+P[i]>boundary) { // update center and boundary
                center = i;
                boundary = i+P[i];
            }
            if(P[i]>maxLen) { // update result
                maxLen = P[i];
                resCenter = i;
            }    
        }
        return s.substr((resCenter - maxLen)/2, maxLen);
    }
};

Manacher 算法

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=917