首页 > 代码库 > 最长回文子串的不同解法

最长回文子串的不同解法

给定一个字符串,返回该字符串的最长回文子串。回文也就是说 。正着读和反着读是一样的。以下总结了几种求回文的方式:

方法1 : 非常easy,枚举全部的区间 [i,j] ,查看该范围内是否是一个回文.

  时间复杂度 O(n^3),空间复杂度 O(1).

方法2: 方法1的时间复杂度太高,而且存在着大量的反复运算。能够使用DP来解。而且保存已经检查过的字符串的状态.

  时间复杂度: O(n^2)。空间复杂度O(n^2).

这里存在两种DP的方法,是依据区间来进行DP,还是长度。只是都是大同小异,不改变整个算法的时间复杂度。

代码例如以下:

//dp 1
string LongestPalindrome(const string &s)
{
    const int n = s.size();
    if(n < 2) return s;
    bool f[n][n+1];

    fill_n(&f[0][0],n*(n+1),false);
    int start = 0, len = 1;

    f[0][0] = true;
    for(int i=0;i<n;++i)
    {
        f[i][0] = true;
        f[i][1] = true;
    }
    for(int i=n-2;i>=0;--i)
    {
        for(int j=2;j<=n && (i+j-1)<n;++j)
        {
            f[i][j] = f[i+1][j-2] && s[i] == s[i+j-1];
            if(f[i][j] && j > len) {start = i; len = j;}
        }
    }

    return s.substr(start,len);
}

//dp 2
string LongestPalindrome_dp2(const string &s)
{
    const int n = s.size();
    if(n < 2) return s;
    bool f[n][n];

    fill_n(&f[0][0],n*n,false);
    int start=0,len=1;
    f[0][0] = true;

    for(int i=0;i<n;++i)
        f[i][i] = true;

    for(int i = n-1 ; i >= 0; --i)
    {
        for(int j = i+1; j < n;++j)
        {
            if(j == i+1) f[i][j] = (s[i] == s[j]);
            else
                f[i][j] = f[i+1][j-1] && s[i] == s[j];
            if(f[i][j] && (j-i+1) > len) {start = i; len = j-i+1;}
        }
    }

    return s.substr(start,len);
}

方法3: 非常直观的想法。以每个字符串为中心,计算该字符串左右能够延伸的部分。注意处理长度为奇数和偶数的情况。

时间复杂度 : O(n^2) 。空间复杂度 : O(1)

//从中间往两端延伸(考虑奇数偶数的情况就可以)

string LongestPalindrome_extend(const string &s)
{
    const int n = s.size();
    if(n < 2) return s;
    int low,high;
    int start=0,len=1;
    for(int i=1;i<n;++i)
    {
        //even
        low = i-1;
        high = i;
        while(low>=0&&high<n&&s[low]==s[high])
        {
            if(high-low+1>len)
            {
                start=low;
                len=high-low+1;
            }
            --low;++high;
        }
        //odd
        low = i-1;
        high = i+1;
        while(low>=0&&high<n&&s[low]==s[high])
        {
            if(high-low+1 > len)
            {
                start = low;
                len=high-low+1;
            }
            --low;++high;
        }
    }
    return s.substr(start,len); 
}


方法4:使用后缀数组的思想,将字符串s取s的逆,拼接在s的后面,也就是说 如今考察的字符串是 s#s‘。当中的#是额外的一个字符,s‘是s的逆串。求当前这个新拼接而成的字符串的后缀树组的最长公共前缀。

时间复杂度: O(n^2),空间复杂度 O(n^2)

//关于此方法还没想明确。暂不贴代码



方法5: manacher算法。此算法也就是直接參考的上述的方法3,以每个点为中心,来计算左右能够延伸的部分,可是这个方案存在冗余的比較,manacher则是利用已经有的信息,尽可能的降低冗余的信息。

详细请參考 点击打开链接。

以下的图是我对manacher算法的理解,manacher算法事实上就是计算一个数组。数组中的每个元素表示以当前元素为中心的回文的长度。事实上是非常easy的,仅仅要分情况来讨论就能够了。


技术分享

对上述的理解,当前须要计算的位置的index为 i,此时的最右端的位置是right,这个right相应的回文的中心为idx。

分两种情况来讨论:

1  right  <=  i , 也就是最以下的一幅图,非常显然之前计算过的回文的信息对于计算此时的 i 的回文是全然没有帮助的,也就是说。此时 须要以 i 为中心一个一个的去匹配就可以。

2   right  > i , 也就是中间3三幅图的情况,图中的 j  表示以 idx  为对称中心的 i 的对称点的位置, 显然  j = 2 * id - i 。

这里又分两种情况:

     1) 假设以 j 为中心的回文子串的左边界超出了以idx为中心的回文(图4)。那么这时的 i 的回文子串的长度除了至少能够到达right。 至于超出right的部分,仅仅好一个一个的去匹配了。

     2) 假设以j为中心的回文子串的左边界没有超出以idx为中心的回文。那么直接就是j的回文的长度就可以。


也就是说, 假设  i > right  ,那么P[right] = 1;

                    假设 i  < right。此时的 P[i] 的值取决于 i 关于 idx 的对称点 j 的 P[j]的值 。 假设 i + P[j] > right ,那么P[i] = right-i ,余下的部分一个一个的去匹配。  假设 i + P[j] < right。那么P[i] = P[j] ,剩下的一个一个去匹配。

 


时间复杂度 : O(n), 空间复杂度 O(n).


代码为:

//Manacher O(n)
string Manacher(const string &str)
{
    //add ‘#‘
    string s = "$";
    for(auto a : str)
    {
        s += ‘#‘;
        s += a;
    }
    s += ‘#‘;
    cout << s << endl;
    const int n = s.size();
    vector<int> P(n,0);
    int right = -1, idx = -1;    //right记录当前已经计算过的回文的最右边的边界(这个边界是不包括在回文中的)
    for(int i=1;i<n;++i)
    {
        P[i] = (right > i)? min(P[2*idx-i],right-i):1; //这一句就是整个算法的核心!

!!

while(s[i+P[i]] == s[i-P[i]])P[i]++; if(i+P[i]>right) { right = i + P[i]; idx = i; } } auto pos = max_element(P.begin(),P.end()); int len = *pos-1; string ret; int i = pos-P.begin(); //print ret += s[i]; cout << ret << endl; int k=1; while(len) { ret += s[i+k]; ret = s[i-k]+ret; cout << ret << endl; ++k; --len; } //trim # string ret2; for(auto a :ret) if(a!=‘#‘)ret2 += a; return ret2; }


上述代码均已验证正确。至于原理,全在代码中。


最长回文子串的不同解法