在一個字符串中要到最長的回文子串，有如下方案，代碼在最后。

最長回文子串的相關(guān)博文

1、暴力法

最容易想到的就是暴力破解，求出每一個子串，之后判斷是不是回文，找到最長的那個。

求每一個子串時間復(fù)雜度O(N^2)，判斷子串是不是回文O(N)，兩者是相乘關(guān)系，所以時間復(fù)雜度為O(N^3)。

2、中心擴(kuò)展

中心擴(kuò)展就是把給定的字符串的每一個字母當(dāng)做中心，向兩邊擴(kuò)展，這樣來找最長的子回文串。算法復(fù)雜度為O(N^2)。
但是要考慮兩種情況：
1）長度為奇數(shù)。
2）長度為偶數(shù)。

3、動態(tài)規(guī)劃
回文字符串的子串也是回文，因此用dpm[i,j]（表示以i開始以j結(jié)束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。這樣最長回文子串就能分解成一系列子問題了。這樣需要額外的空間O（N^2)，算法復(fù)雜度也是O(N^2)。
首先定義狀態(tài)方程和轉(zhuǎn)移方程：?dpm[i,j]=0表示子串[i,j]不是回文串。dpm[i,j]=1表示子串[i,j]是回文串。

4、Manacher法
Manacher法只能解決例如aba這樣長度為奇數(shù)的回文串，對于abba這樣的不能解決，于是就在里面添加特殊字符。一般添加了“#”，使abba變?yōu)閍#b#b#a。這個算法就是利用已有回文串的對稱性來計算的，具體算法復(fù)雜度為O(N)。

Manacher詳細(xì)介紹

下面是幾種方法的代碼

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);vector<vector<bool>> dpm(sl, vector<bool>(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 '#'vector<int> 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);vector<int> 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); }

其中：

函數(shù)isPalindrome 檢查一個子串是否為回文子串；

findLongestPalindromeBrute 為暴力方案；

findLongestPalindromeDP 為動態(tài)規(guī)劃；

findLongestPalindromeCE 為中心擴(kuò)展；

findLongestPalindromeManacher 和?findLongestPalindromeManacher2 為?Manacher方案。

轉(zhuǎn)載于:https://www.cnblogs.com/lmjy/p/6858220.html

總結(jié)

以上是生活随笔為你收集整理的最长回文子串 C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。