网站专门做冻品的,免费咨询范围,广州市网站制作,芭嘞seo在一个字符串中要到最长的回文子串#xff0c;有如下方案#xff0c;代码在最后。 最长回文子串的相关博文 1、暴力法 最容易想到的就是暴力破解#xff0c;求出每一个子串#xff0c;之后判断是不是回文#xff0c;找到最长的那个。 求每一个子串时间复杂度O(N^2)#x… 在一个字符串中要到最长的回文子串有如下方案代码在最后。 最长回文子串的相关博文 1、暴力法 最容易想到的就是暴力破解求出每一个子串之后判断是不是回文找到最长的那个。 求每一个子串时间复杂度O(N^2)判断子串是不是回文O(N)两者是相乘关系所以时间复杂度为O(N^3)。 2、中心扩展 中心扩展就是把给定的字符串的每一个字母当做中心向两边扩展这样来找最长的子回文串。算法复杂度为O(N^2)。 但是要考虑两种情况 1长度为奇数。 2长度为偶数。 3、动态规划 回文字符串的子串也是回文因此用dpm[i,j]表示以i开始以j结束的子串是回文字符串那么P[i1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间ON^2)算法复杂度也是O(N^2)。 首先定义状态方程和转移方程 dpm[i,j]0表示子串[i,j]不是回文串。dpm[i,j]1表示子串[i,j]是回文串。 4、Manacher法 Manacher法只能解决例如aba这样长度为奇数的回文串对于abba这样的不能解决于是就在里面添加特殊字符。一般添加了“#”使abba变为a#b#b#a。这个算法就是利用已有回文串的对称性来计算的具体算法复杂度为O(N)。 Manacher详细介绍 下面是几种方法的代码 inline bool isPalindrome(const string s,int n1, int n2) {for (int k1(n1), k2(n2 - 1); k1 k2; k1, --k2) if (s[k1] ! s[k2]) return false;return true;
}string findLongestPalindromeBrute(string s) {int sl(s.length()), mlen(1), start(0);for (int k1(0); k1 sl; k1) {for (int k2(k1 mlen 1); k2 sl; k2) {if (isPalindrome(s, k1, k2)) start k1, mlen k2 - k1;}}return s.substr(start, mlen);
}string findLongestPalindromeDP(string s) {int sl(s.length()), mlen(1), start(0);vectorvectorbool dpm(sl, vectorbool(sl, false));for (int k1(0); k1 sl; k1) dpm[k1][k1] true;for (int k1(0); k1 sl - 1; k1) {if (s[k1] s[k1 1]) {dpm[k1][k1 1] true;if (!start) start k1, mlen 2;}}for (int kn(3); kn sl; kn) {for (int k1(0); k1 sl - kn; k1) {if (dpm[k1 1][k1 kn - 2] s[k1] s[k1 kn - 1]) {dpm[k1][k1 kn - 1] true;mlen kn;start k1;}}}return s.substr(start, mlen);
}string findLongestPalindromeCE(string s) {int sl(s.length()), mlen(1), start(0);for (int k1(1), kd(1); k1 sl; k1) {for (kd 1; k1 - kd 0 k1 kd sl s[k1 - kd] s[k1 kd];kd);if (mlen 2 * kd - 1) {mlen 2 * kd - 1;start k1 - kd 1;}}for (int k1(1), kd; k1 sl; k1) {for (kd 0; k1 - kd 0 k1 kd 1 sl s[k1 - kd] s[k1 kd 1]; kd);if (mlen 2 * kd) {mlen 2 * kd;start k1 - kd 1;}}return s.substr(start, mlen);
}string findLongestPalindromeManacher(string s) {string s1($#);for (auto ch : s) s1 ch, s1 #; // Insert #vectorint pv(s1.size(), 0);int index(0), mlen(1);for (int k1(2),mid(1),mxr(0); k1 s1.size(); k1) {pv[k1] k1 mxr ? min(pv[mid mid - k1], mxr - k1) : 1;while (s1[k1 pv[k1]] s1[k1 - pv[k1]]) pv[k1];if (mxr k1 pv[k1]) {mxr k1 pv[k1];mid k1;}if (mlen pv[k1]) {mlen pv[k1];index k1;}}return s.substr((index - mlen) / 2, mlen - 1);
}
string findLongestPalindromeManacher2(string s) {string s1(#);for (auto ch : s) s1 ch, s1 #; // Insert #int sl1(s1.length()), index(0), mlen(1);vectorint pv(sl1, 0);for (int k1(1), kd(1), kt; k1 sl1;) {while (0 k1 - kd k1 kd sl1 s1[k1 - kd] s1[k1 kd]) kd;pv[k1] kd - 1;for (kt 1; kt pv[k1] pv[k1 - kt] pv[k1] - kt; kt) pv[k1 kt] pv[k1 - kt];k1 kt;kd kd - kt;}for (int k1(1); k1 sl1; k1) {if (mlen pv[k1]) {mlen pv[k1];index k1;}}return s.substr((index - mlen) / 2, mlen);
} 其中 函数isPalindrome 检查一个子串是否为回文子串 findLongestPalindromeBrute 为暴力方案 findLongestPalindromeDP 为动态规划 findLongestPalindromeCE 为中心扩展 findLongestPalindromeManacher 和 findLongestPalindromeManacher2 为 Manacher方案。 转载于:https://www.cnblogs.com/lmjy/p/6858220.html
