做新房什么网站好,wordpress带登陆主题,运输网站建设,酒店网站程序题目来自lintcode, 链接#xff1a;http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/ 最长回文子串 给出一个字符串#xff08;假设长度最长为1000#xff09;#xff0c;求出它的最长回文子串#xff0c;你可以假定只有一个满足条件的最长回文串。… 题目来自lintcode, 链接http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/ 最长回文子串 给出一个字符串假设长度最长为1000求出它的最长回文子串你可以假定只有一个满足条件的最长回文串。 样例 给出字符串 abcdzdcab它的最长回文子串为 cdzdc。 挑战 O(n2) 时间复杂度的算法是可以接受的如果你能用 O(n) 的算法那自然更好。 一. 首先给出O(n^2)的算法 思路dp[i][k]表示第i个位置开始长度为k的串的最大回文串的长度, jik-1 当 s[i] s[j] dp[i1][k-2] k-2, dp[i][k] dp[i1][k-2] 2; 否则 dp[i][k] max(dp[i1][k-1], dp[i][k-1]); 并记录dp[i][k]的最大值最后找到最长回文子串的区间。 int dp[1005][1005];string longestPalindrome(string s) {// Write your code hereO(n^2)int len s.size();memset(dp, 0, sizeof(dp));for(int i0; ilen; i)dp[i][1] 1;int ld0, rd0, maxL 1;for(int k2; klen; k){for(int i0, j; ilen (jik-1)len; i){if(s[i] s[j] dp[i1][k-2] k-2)dp[i][k] dp[i1][k-2] 2;else dp[i][k] max(dp[i1][k-1], dp[i][k-1]);if(maxLdp[i][k]){maxL dp[i][k];ld i;rd j;}}}return s.substr(ld, rd-ld1); } 二.然后看一下复杂度为O(n)的Manacher算法 2.1 先说一下这个算法的思想 用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度包括S[i]。 2.2 算法基本要点 这个算法不能求出最长回文串长度为偶数回文串。用一个非常巧妙的方式将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度在相邻两个字符之间插入一个特殊的符号。比如 abba 变成 a#b#b#a。 为了进一步减少编码的复杂度可以在字符串的开始加入另一个特殊字符这样就不用特殊处理越界问题比如$a#b#b#a。 2.3 具体说一个例子 S[] 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 P[] 1 1 2 1 2 1 4 1 2 1 5 1 2 1 1 (p.s. 可以看出P[i]-1正好是原字符串中回文串的总长度 2.4 为啥要对字符串进行处理插入# 如果不对字符进行处理, 对于最长回文串为偶数的情况下 S[] 1 2 1 1 2 1 P[] 1 2 1 1 2 1 对字符进行处理对于最长回文串为偶数的情况下 S[] 1 # 2 # 1 # 1 # 2 # 1 P[] 1 1 3 1 2 6 2 1 3 1 1 可见不对字符进行处理对于最长回文串为偶数的情况是不能得到最大的回文串的长度。 2.5 如何计算P数组的值: 算法增加两个辅助变量id和mx其中id表示最大回文子串中心的位置mx则为idP[id]也就是最大回文子串的边界。 当 mx - i P[j] 的时候以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中由于 i 和 j 对称以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中所以必有 P[i] P[j]见下图。 当 P[j] mx - i 的时候以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中但是基于对称性可知下图中两个绿框所包围的部分是相同的也就是说以S[i]为中心的回文子串其向右至少会扩张到mx的位置也就是说 P[i] mx - i。至于mx之后的部分是否对称就只能一个一个匹配了。 对于 mx i 的情况无法对 P[i]做更多的假设只能P[i] 1然后再去匹配了。 2.6 寻找最大长度的回文子串 看一种情况 S[] 1 # 2 # 2 P[] 1 1 2 2 1 首先 P中的最大值为2但是最大值有两个我们应该选择哪一个其实如果P中的最大值对应的字符不是#显然不能得到最大长度的回文串。所以当我们遇到这种情况时(maxP P[i] S[i]#)要更新最大值所在位置。 2.7 最后代码 class Solution {
public:/*** param s input string* return the longest palindromic substring*/string manacher(string str){int *p new int[str.size()]();memset(p, 0, sizeof(p));int mx 0, id 0;for(int i1; istr.size(); i){if(mx i)p[i] min(p[2*id-i], mx-i);elsep[i] 1;while(str[i - p[i]] str[i p[i]])p[i];if(i p[i] mx){mx i p[i];id i;}}//寻找数组P中的最大值的位置int maxP 0;for(int i1; istr.size(); i)if(maxP p[i] || (maxP p[i] str[i]#)){maxP p[i];id i;} //根据id确定最长回文串的区间int ld id-p[id]1, rd idp[id]-1;string ans ;for(int ild; ird; i)if(str[i]!#)ans str[i];return ans;}string longestPalindrome(string s) {// Write your code here//采用manacher算法O(n)的时间复杂度int len s.size(); //首先预处理字符串每两个字符之间插入#int k -1;for(int i1; ilen; i)s.insert(k2, 1, #);s.insert(0, 1, $);return manacher(s);}
}; 转载于:https://www.cnblogs.com/hujunzheng/p/5033891.html
