1. Longest Palindromic Substring ( 最長回文子串 )

要求: Given a string S, find the longest palindromic substring in S. (从字符串 S 中最长回文子字符串。)

何为回文字符串? A palindrome is a string which reads the same in both directions. For example, “aba” is a palindome, “abc” is not.

解决方法:参考:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

1.暴力法(Brute force solution)

共 C(N, 2) 个子串。时间复杂度O(N3)

2.后缀树法(Suffix tree solution)

反转 S 得到 S' ,例如:S = “caba”, S’ = “abac”. 求最长公共子串。求最大公共子串方法有后缀树或动态规划方法。 

可参考:http://en.wikipedia.org/wiki/Longest_common_substring

注意陷阱:例如,S = “abacdfgdcaba”, S’ = “abacdgfdcaba”. 最长公共子串是 “abacd” ,明显不是回文串。

陷阱原因:S 中有它的非回文子串的反转出现。

克服方法:对于找到的公共子串,查找它在两个母串的全部下标是否都相等。

3.动态规划法(Dynamic programming solution)

 时间复杂度 O(N2), 空间复杂度  O(N2)。

定义数组:

则有,1. Longest Palindromic Substring  ( 最長回文子串 )

          dp[i][j] = d[i+1][j-1] && S[i] == S[j]

初始条件:

          dp[i][i] = ture , i = 1,……,s.length() -1.

          dp[i][i+1] =  (S[i] == S[i+1]) , i = 1,……,s.length()-2

代码:

class Solution {
public:
    string longestPalindrome(string s) {
        /**************  动态规划  *************/
        int n = s.length();
        if(n == 0) return "";
        bool dp[1][1] = {false};
        int firstIndex = 0, maxLen = 1;
        for(int r = 0; r <= n - 1; ++r) {
            for(int index = 0; index <= n - 1 - r; ++index) {
                if(s[index] == s[index + r]){
                    if(r < 2){
                        dp[index][index + r] = true;
                        firstIndex = index;
                        maxLen = r + 1;
                    }else if(dp[index + 1][index + r -1] == true){
                        dp[index][index + r] = true;
                        firstIndex = index;
                        maxLen = r + 1;
                    }
                }
            }
        }
    return s.substr(firstIndex, maxLen);
    }
};

 4.更简单的方法

O(N2)时间,O(1)空间

分析:回文串一定有一个中心,然后关于中心对称。长度为 N 的字符串有潜在的对称中心数目为 N + (N - 1) = 2N -1。

基于每个中心去找时间复杂度为 O(N),共查找 2N-1 次。因此总的时间复杂度为 O(N(2N - 1)) ~ O(N2).

代码:

string expandAroundCenter(string s, int left, int right){
    int n = s.length();
    while(left >= 0 && right <= n - 1 && s[left] == s[right]){
        --left;
        ++right;
    }
    return s.substr(left + 1, right - left - 1);
}

class Solution {
public:
    string longestPalindrome(string s) {
        /**************  O(n^2)time, O(1)space complexity *************/
        int n = s.length();
        if(n == 0) return "";
        string longest = s.substr(0,1);
        for(int index = 0; index < n; ++index){
            string s1 = expandAroundCenter(s, index, index);
            string s2 = expandAroundCenter(s, index, index + 1);
            if(s1.length() > s2.length()){
                if(s1.length() > longest.length()) longest = s1;
            }else if(s2.length() > longest.length()) longest = s2;
        }
        return longest;
    }
};

5.Manacher’s Algorithm

时间复杂度 O(N),空间复杂度 O(4N)

算法思路:第一步:对于输入的长度为 N 的字符串 S,在字符间的 N+1 个位置分别插入一个特殊符号 "#",得到新的字符串 T ,长度为 2N+1。

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

第二步:定义数组 P[2N+1]。分别以 T 中每个字符为回文串的中心,查找它的半径的值,结果存放在 P 中。(注意:数组 P 中最大数等于 S 中最大回文子串的长度)

例如:

1. Longest Palindromic Substring  ( 最長回文子串 )
 (则 S 的最大回文子串长度为 6)。

(注意:P 中数字关于中心对称)

接下来,主要就是对第二步的分析和优化。

以下面比较复杂的字符串为例:(可以看英文解释,也可以看我的叙述)

1. Longest Palindromic Substring  ( 最長回文子串 )

 

 变量解释:L 和 R 分别为以 C 为中心的回文串的左右边界,其中 L + R = 2*C。分析两种情况:

index13  关于 C 对称点为 index(2*c-13) ,即 index9 ,因为 P[9] = 1,而且 P[9] < R-12(小于左边界) ,所以 P[13] = P[9] = 1;

……

index15  关于 C 对称点为 index(2*c-15) ,即 index7 ,因为 P[7] = 7,而且 P[7] >= R-15(大于左边界) ,所以 :

首先令P[15] = P[7] = 7,然后令 C =  15,以 index15 为中心,以 T[15-P[15]-1] 和 T[15+P[15]+1] 开始比较,向两段延伸,找新的 L 和 R.

最后得到 P[15] =  13 ,L = 2,R = 8。

……

代码:(为了方便边界,两边加了的特殊符号)

string preprocess(string s){
    int n = s.length();
    if(n == 0) return "";
    string newS = "^#";
    for(int i = 0; i < n; ++i)
        newS += "#" + s.substr(i,1);
    newS += "#$";
    return newS;
}

class Solution {
public:
    string longestPalindrome(string s) {
        /**************  O(n)time, O(4n)space complexity *************/
        string T = preprocess(s);
        int n = T.length();
        if(n == 0) return "";
        int *p = new int[n];
        int C = 0, R = 0;
        int maxLen = 1, firstIndex = 0; 
        for(int i = 1; i < n-2; ++i){
            int i_mirror = 2 * C - i;
            p[i] = (R > i) ? min(R - i, p[i_mirror]) : 0;
            while(T[i + p[i] + 1] == T[i - p[i] - 1]) {
                ++p[i];
                if(p[i] > maxLen){
                    maxLen = p[i];
                    firstIndex = (i - 1 - p[i]) / 2;
                }
            }
            if(i + p[i] > R){
                C = i;
                R = i + p[i];
            }
        }
        return s.substr(firstIndex, maxLen);
    }
};

 

 

 

 

 

更多相关文章
一周排行
  • 


    		    Python結合selenium自動領取無憂幣的腳本
    首先申明,我并没有使用此脚本来恶意领取无忧币,不要封我账号啊,呵呵,我记得以前在oschi
  • 服务端跟新浪微博交互的时候需要用到UID参数, 但WP的WeiboSDK默认没有提供, 只要增加一个类成员就好了, 序列化json的时候程序会自动处理   下载SDK源代码http://weibowp7sdk.cod ...
  • 


    		    SCVMM2012功能測試(13)—動態優化
    13-动态优化 动态优化需要用到SCOM服务器,所以需要创建一个运行方式帐户,该帐户需要有
  • 回想以前,想要安装个虚拟机是多么的麻烦.先要费尽心机找到想要的操作系统镜像文件,然后安装虚拟化软件,按照其提供的GUI界面操作一步步创建,整个过程费时费力.但是,自从使用了Vagrant以后,咱腰不酸了,腿不痛了,一
  • Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni+1, .. ...
  • Mac 系统自带GIT,但是自带的GIT 版本很老,也没有自动提示和gitk等功能,如果一个一个去安装非常的费劲. 我们采用brew 安装git 非常的方便,但是,我们发现安装后没有任何作用,因为默认使用的GIT还是
  • 二、利用EnterpriseFrameWork快速開發Web系統(B/S)
    EnterpriseFrameWork框架实例源代码下载: 实例下载           
  • RS485是一个物理接口,简单的说是硬件. MODBUS是一种国际标准的通讯协议,用于不同厂商之间的设备交换数据(一般是工业用途):所谓协议,也可以理解为上面有人说的“语言”吧,简单的说是软件. RS485属于有线传 ...
  • 前段时间做OA系统的https的安全登录功能(以前登录是采用的一般的http方式,后因为安全性考虑需要改成https的方式)在本机测试完全通过. 可是近期同事发现在测试环境下用IE6访问会出现不能访问的问题.我测试了 ...
  • 多校7 1005 The shortest problem
    The shortest problem Time Limit: 3/1500 MS (J