Longest Palindromic Substring-阿里云开发者社区

开发者社区> 人工智能> 正文

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, and there exists one unique longest palindromic substring. 求字符串的最长回文子串   算法1:暴力解法,枚举所有子串,对每个子串判断是否为回文,复杂度为O(n^3) 算法2:删除暴力解法中有很多重复的判断。

动态规划

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

求字符串的最长回文子串

 

算法1:暴力解法,枚举所有子串,对每个子串判断是否为回文,复杂度为O(n^3)


算法2:删除暴力解法中有很多重复的判断。很容易想到动态规划,时间复杂度O(n^2),空间O(n^2),动态规划方程如下:

  • dp[i][j] 表示子串s[i…j]是否是回文
  • 初始化:dp[i][i] = true (0 <= i <= n-1);  dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化为false
  • dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true)

在动态规划中保存最长回文的长度及起点即可。

C++实现代码:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

class Solution
{
public:
    string longestPalindrome(string s)
    {
        if(s.empty())
            return NULL;
        int start=0;
        int end=0;
        int n=s.length();
        bool dp[n][n];
        memset(dp,false,sizeof(dp));
        int i;
        dp[0][0]=true;
        for(i=1;i<n;i++)
        {
            dp[i][i]=true;
            dp[i][i-1]=true;
        }
        int k;//k用于记录从i开始的子串的长度,当长度为1是肯定是回文,从len=2开始判断
        for(k=2;k<=n;k++)
        {
            for(i=0;i<=n-k;i++)
            {
                if(s[i]==s[i+k-1]&&dp[i+1][i+k-2])
                {
                    dp[i][i+k-1]=true;
                    if(k>end-start+1)
                    {
                        start=i;
                        end=i+k-1;
                    }
                }
            }
        }
        return s.substr(start,end-start+1);
    }
};

int main()
{
    string s1="bbb";
    Solution s;
    cout<<s.longestPalindrome(s1)<<endl;
}

思路3. 思路来源于此

http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

不过原文的陈述仔细研究了一下,有一些地方让人着实费解,所以自己决定重写一遍。

这里描述了一个叫Manacher’s Algorithm的算法。

算法首先将输入字符串S, 转换成一个特殊字符串T,转换的原则就是将S的开头结尾以及每两个相邻的字符之间加入一个特殊的字符,例如#

 

例如: S = “abaaba”, T = “#a#b#a#a#b#a#”.

为了找到最长的回文字串,例如我们当前考虑以Ti为回文串中间的元素,如果要找到最长回文字串,我们要从当前的Ti扩展使得 Ti-d … Ti+d 组成最长回文字串. 这里 d 其实和 以Ti为中心的回文串长度是一样的. 进一步解释就是说,因为我们这里插入了 # 符号,对于一个长度为偶数的回文串,他应该是以#做为中心的,然后向两边扩,对于长度是奇数的回文串,它应该是以一个普通字符作为中心的。通过使用#,我们将无论是奇数还是偶数的回文串,都变成了一个以Ti为中心,d为半径两个方向扩展的问题。并且d就是回文串的长度。

例如 #a#b#a#, P = 0103010, 对于b而言P的值是3,是最左边的#,也是延伸的最左边。这个值和当前的回文串是一致的。

如果我们求出所有的P值,那么显然我们要的回文串,就是以最大P值为中心的回文串。

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

例如上面的例子,最长回文是 “abaaba”, P6 = 6.

根据观察发现,如果我们在一个位置例如 abaaba的中间位置,用一个竖线分开,两侧的P值是对称的。当然这个性质不是在任何时候都会成立,接下来就是分析如何利用这个性质,使得我们可以少算很多P的值。

下面的例子 S = “babcbabcbaccba” 存在更多的折叠回文字串。


C表示当前的回文中心,L和R处的线表示以C为中心可以到达的最左和最右位置,如果知道这些,我们如何可以更好的计算C后面的P[i]. 
假设我们当前计算的是 i = 13, 根据对称性,我们知道对称的那个下标 i' = 9. 

根据C对称的原则,我们很容易得到如下数据 P[ 12 ] = P[ 10 ] = 0, P[ 13 ] = P[ 9 ] = 1, P[ 14 ] = P[ 8 ] = 0).

Now we are at index i = 15, and its mirrored index around C is i’ = 7. Is P[ 15 ] = P[ 7 ] = 7?

当时当i = 15的时候,却只能得到回文 “a#b#c#b#a”, 长度是5, 而对称 i ' = 7 的长度是7. 


如上图所示,如果以 i, i' 为中心,画出对称的区域如图,其中以i‘ = 7 对称的区域是 实心绿色 + 虚绿色 和 左侧,虚绿色表示当前的对称长度已经超过之前的对称中心C。而之前的P对称性质成立的原因是 i 右侧剩余的长度 R - i 正好比 以 i‘ 为中心的回文小。 
这个性质可以这样归纳,对于 i 而言,因为根据C对称的最右是R,所以i的右侧有 R - i 个元素是保证是 i' 左侧是对称的。 而对于 i' 而言他的P值,也就是回文串的长度,可能会比 R-i 要大。 如果大于 R - i, 对于i而言,我们只能暂时的先填写 P[i] = R - i, 然后依据回文的属性来扩充P[i] 的值; 如果P[i '] 小于R-i,那么说明在对称区间C内,i的回文串长度和i' 是一样长的。例如我们的例子中 i = 15, 因为R = 20,所以i右侧 在对称区间剩余的是 R - 15 = 5, 而 i’ = 7 的长度是7. 说明 i' 的回文长度已经超出对称区间。我们只能使得P[i] 赋值为5, 然后尝试扩充P[i]. 
if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥R – i. (这里下一步操作是扩充 P[ i ].

扩充P[i] 之后,我们还要做一件事情是更新 R 和 C, 如果当前对称中心的最右延伸大于R,我们就更新C和R。在迭代的过程中,我们试探i的时候,如果P[i'] <= R - i, 那么只要做一件事情。 如果不成立我们对当前P[i] 做扩展,因为最大长度是n,扩展最多就做n次,所以最多做2*n。 所以最后算法复杂度是 O(n)

或许贴上代码更容易一些。直接使用大神的代码了,虽然自己也实现了,不过是理解大神的思路实现的。

C++实现代码:

#include<iostream>
#include<string>
#include<cstring>
#include<new>
using namespace std;

class Solution
{
public:
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
    string preProcess(string s)
    {
        int n = s.length();
        if (n == 0) return "^$";
        string ret = "^";
        for (int i = 0; i < n; i++)
            ret += "#" + s.substr(i, 1);

        ret += "#$";
        return ret;
    }

    string longestPalindrome(string s)
    {
        string T = preProcess(s);
        int n = T.length();
        int *P = new int[n];
        int C = 0, R = 0;
        for (int i = 1; i < n-1; i++)
        {
            int i_mirror = 2*C-i; // equals to i' = C - (i-C)

            P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

            // Attempt to expand palindrome centered at i
            while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
                P[i]++;

            // If palindrome centered at i expand past R,
            // adjust center based on expanded palindrome.
            if (i + P[i] > R)
            {
                C = i;
                R = i + P[i];
            }
        }
        for(int k=0;k<n;k++)
            cout<<P[k]<<" ";
        cout<<endl;
        // Find the maximum element in P.
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n-1; i++)
        {
            if (P[i] > maxLen)
            {
                maxLen = P[i];
                centerIndex = i;
            }
        }
        delete[] P;

        return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
    }
};

int main()
{
    string s1="abaaba";
    Solution s;
    cout<<s.longestPalindrome(s1)<<endl;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章