一、基本概念

回文字符串：是一個正讀和反讀都一樣的字符串。

?

?

?

二、問題與算法

（1）判斷

思想：

1、初始化標志flag=true；

2、輸入字符串str，并獲取其長度len；

3、定義并初始化游標i=0，j=len-1，分別指向字符串開頭和末尾；

4、比較字符str[i]和str[j],若i==j，轉至7，否則往下執行5；

5、若str[i]和str[j]相等，則游標i加1，游標j減1后轉至4，否則往下執行6；

6、令標志位flag=flase，結束比較，str不是回文串，算法結束。

7、若str[i]和str[j]相等，結束比較，flag=true,str為回文串，算法結束。

?C++版本一

#include <stdio.h> #include <string.h>int main() {char a[100]= {0};int i = 0;int len = 0;gets(a);len = strlen(a); //計算輸入字符串的長度；for(i = 0; i < (len / 2); i++) //只需要判斷前一半（len/2）長度就好了{ if(a[i] != a[len - 1 - i]) //判斷是否為回文數；{printf("不是回文數\n");return 0;}}printf("是回文數\n");return 0; }

（2）最長回文子串(Longest_Palindromic_Substring)

1、樸素

思想：

1）從最長的子串開始，遍歷所有該原字符串的子串；

2）每找出一個字符串，就判斷該字符串是否為回文；

3）子串為回文時，則找到了最長的回文子串，因此結束；反之，則繼續遍歷。

C++版本一

/* * 判斷str[i...j]是否是回文串 */ bool isPalindrome(const char *str, int begin, int end) {while (begin <= end){if (str[begin] == str[end]){begin++;end--;}elsereturn false;}return true; }/* *返回字符串str的最長回文子串的長度 */ int longestPalindrome(const char *str) { if (str == NULL) return 0; int len = strlen(str); if (len == 1) return 1; int longest = 1; for (int i = 0; i < len; i++)for (int j = i + 1; j < len; j++)if (isPalindrome(str, i, j) == true)longest = longest < j - i + 1 ? j - i + 1 : longest; return longest; }

JAVA版本一

?public static String longestPalindrome(String s) {if(s.length() <= 1)return s;for(int i = s.length();i > 0; i--) {//子串長度for (int j = 0; j <= s.length() - i; j++) {String sub = s.substring(j , i + j);//子串位置int count = 0;//計數，用來判斷是否對稱for (int k = 0; k < sub.length() / 2; k++) {//左右對稱判斷if (sub.charAt(k) == sub.charAt(sub.length() - k - 1))count++;}if (count == sub.length() / 2)return sub;}}return "";//表示字符串中無回文子串}

2、中心擴散

思想：

1）將子串分為單核和雙核的情況，單核即指子串長度為奇數，雙核則為偶數；

2）遍歷每個除最后一個位置的字符index(字符位置)，單核：初始low = 初始high = index，low和high均不超過原字符串的下限和上限；判斷low和high處的字符是否相等，相等則low++、high++（雙核：初始high = 初始low+1 = index + 1）；

3）每次low與high處的字符相等時，都將當前最長的回文子串長度與high-low+1比較。后者大時，將最長的回文子串改為low與high之間的；

4）重復執行2）、3），直至high-low+1 等于原字符串長度或者遍歷到最后一個字符，取當前截取到的回文子串，該子串即為最長的回文子串。
?

?

C++版本一

string longestPalindrome(string s){if(s.empty()) return "";if(s.size()==1) return s;int start=0,maxlength=1;//記錄最大回文子串的起始位置以及長度for(int i=0;i<s.size();i++)for(int j=i+1;j<s.size();j++)//從當前位置的下一個開始算{int temp1,temp2;for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--){if(s[temp1]!=s[temp2])break;}if(temp1>=temp2 && j-i+1>maxlength)//這里要注意條件為temp1>=temp2，因為如果是偶數個字符，相鄰的兩個經上一步會出現大于的情況{maxlength = j-i+1;start=i;}}return s.substr(start,maxlength);//利用string中的substr函數來返回相應的子串,第一個參數是起始位置，第二個參數是字符個數}

JAVA版本一

private static int maxLen = 0;private static String sub = "";public static String longestPalindrome(String s) {if(s.length() <= 1)return s;for(int i = 0;i < s.length()-1;i++){findLongestPalindrome(s,i,i);//單核回文findLongestPalindrome(s,i,i+1);//雙核回文}return sub;}public static? void findLongestPalindrome(String s,int low,int high){while (low >= 0 && high <= s.length()-1){if(s.charAt(low) == s.charAt(high)){if(high - low + 1 > maxLen){maxLen = high - low + 1;sub = s.substring(low , high+1);}low --;//向兩邊擴散找當前字符為中心的最大回文子串high ++;}elsebreak;}}

3、動態規劃

思想：

?對于字符串str，假設dp[i,j]=1表示str[i...j]是回文子串，那個必定存在dp[i+1,j-1]=1。這樣最長回文子串就能分解成一系列子問題，可以利用動態規劃求解了。

首先構造狀態轉移方程

?

上面的狀態轉移方程表示，當str[i]=str[j]時，如果str[i+1...j-1]是回文串，則str[i...j]也是回文串；如果str[i+1...j-1]不是回文串，則str[i...j]不是回文串。

初始狀態

• dp[i][i]=1

• dp[i][i+1]=1 if str[i]==str[i+1]

上式的意義是單個字符，兩個相同字符都是回文串。

?

C++版本一

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 i=0; i<len; ++i)dp[i][1] = 1;int ld=0, rd=0, maxL = 1;for(int k=2; k<=len; ++k){for(int i=0, j; i<len && (j=i+k-1)<len; ++i){if(s[i] == s[j] && dp[i+1][k-2] == k-2)dp[i][k] = dp[i+1][k-2] + 2;else dp[i][k] = max(dp[i+1][k-1], dp[i][k-1]);if(maxL<dp[i][k]){maxL = dp[i][k];ld = i;rd = j;}}}return s.substr(ld, rd-ld+1);}

C++版本二

/* *返回字符串str的最長回文子串的長度 */ int longestPalindrome(const char *str) {if (str == NULL) return 0;int len = strlen(str);if (len == 1)return 1;int longest = 1;int dp[100][100];for (int i = 0; i < len; i++){dp[i][i] = 1;if (str[i] == str[i + 1])dp[i][i + 1] = 1;}for (int i = 0; i < len; i++){for (int j = i + 2; j <= len; j++){if (str[i] == str[j]){dp[i][j] = dp[i][j - 1];if (dp[i][j] == 1){int tmp = j - i + 1;if (longest < tmp)longest = tmp;}}else dp[i][j] = 0;}}return longest; }動態規劃

JAVA版本一

package com.ysw.test;import java.util.Scanner;/** 問題描述：* 給定一個字符串S，找出它的最大的回文子串，你可以假設字符串的最大長度是1000，* 而且存在唯一的最長回文子串 。*/ public class LongestPalindrome {/*** @param args*/public static void main(String[] args) {// 從鍵盤讀入字符串String str = null;Scanner reader = new Scanner(System.in);str = reader.nextLine();System.out.println(getLongestPalindrome(str));}/*** 此方法返回s的最長回文串* * @param str* @return*/private static String getLongestPalindrome(String str) {boolean dp[][];// 如果字符串的長度為0，則認為str的最長回文串為空字符串if (str.length() == 0) {return "";}// 字符串str長度為1.則字符串本身就是一個最長回文串if (str.length() == 1) {return str;}// dp[i][j],表示字符串str從str[i]到str[j]的子串為最長回文子串dp = new boolean[str.length()][str.length()];// 記錄已經找到的最長回文子串的長度int maxLen = 1;// 記錄最長回文子串的起點位置和終點位置int start = 0, end = 0;// 動態規劃的進行是按照字符串的長度從1 到 n推進的，k表示正在判斷的子串的長度// 用于和已知的子串的長度maxLen進行比較int k;// 找出str的所有子串的dp對應的boolean值,初始化過程for (int i = 0; i < str.length(); i++) {for (int j = 0; j < str.length(); j++) {// 當i==j的時候，只有一個字符的字符串// 當i>j的時候認為是空串，dp[i][j]if (i >= j) {dp[i][j] = true;} else {dp[i][j] = false;}}}// 我在這里犯了一個幼稚的錯誤，把i、j的定義放在了for循環中，在else{}中是訪問不到的// 運行程序報java.lang.StringIndexOutOfBoundsException: String index out of// range錯誤int i, j;for (k = 1; k < str.length(); k++) {for (i = 0; i + k < str.length(); i++) {j = i + k;if (str.charAt(i) != str.charAt(j)) {dp[i][j] = false;} else {dp[i][j] = dp[i + 1][j - 1];if (dp[i][j]) {// 判斷找到的子串的長度是否大于我們已知的最長子串的長度if (k + 1 > maxLen) {// 記錄最長回文子串maxLen = k + 1;// 記錄子串的起始位置，因為后面的函數subString(int beginIndex,int// endIndex)函數要用到start = i;end = j;}}}}}return str.substring(start, end + 1);} }

4、Manacher's Algorithm(馬拉車算法)

思想：

?

一）第一步是改造字符串S，變為T，其改造的方法如下：

在字符串S的字符之間和S的首尾都插入一個“#”，如：S=“abba”變為T="#a#b#b#a#" 。我們會發現S的長度是4，而T的長度為9，長度變為奇數了！！那S的長度為奇數的情況時，變化后的長度還是奇數嗎？我們舉個例子，S=“abcba”，變化為T=“#a#b#c#b#a#”，T的長度為11，所以我們發現其改造的目的是將字符串的長度變為奇數，這樣就可以統一的處理奇偶的情況了。

二）第二步，為了改進回文相互重疊的情況，我們將改造完后的T[ i ] 處的回文半徑存儲到數組P[ ]中，P[ i ]為新字符串T的T[ i ]處的回文半徑，表示以字符T[i]為中心的最長回文字串的最端右字符到T[i]的長度，如以T[ i ]為中心的最長回文子串的為T[ l, r ]，那么P[ i ]=r-i+1。這樣最后遍歷數組P[ ]，取其中最大值即可。若P[ i ]=1表示該回文串就是T[ i ?]本身。舉一個簡單的例子感受一下：

數組P有一性質，P[ i ]-1就是該回文子串在原字符串S中的長度 ，那就是P[i]-1就是該回文子串在原字符串S中的長度，至于證明，首先在轉換得到的字符串T中，所有的回文字串的長度都為奇數，那么對于以T[i]為中心的最長回文字串，其長度就為2*P[i]-1,經過觀察可知，T中所有的回文子串，其中分隔符的數量一定比其他字符的數量多1，也就是有P[i]個分隔符，剩下P[i]-1個字符來自原字符串，所以該回文串在原字符串中的長度就為P[i]-1。【這段解釋引用?dyx心心】

另外，由于第一個和最后一個字符都是#號，且也需要搜索回文，為了防止越界，我們還需要在首尾再加上非#號字符，實際操作時我們只需給開頭加上個非#號字符，結尾不用加的原因是字符串的結尾標識為'\0'，等于默認加過了。這樣原問題就轉化成如何求數組P[ ]的問題了。

三）如何求數組P [ ]

? 從左往右計算數組P[ ]， Mi為之前取得最大回文串的中心位置，而R是最大回文串能到達的最右端的值。

? 1）當 i <=R時，如何計算 P[ i ]的值了？毫無疑問的是數組P中點 i 之前點對應的值都已經計算出來了。利用回文串的特性，我們找到點 i 關于 Mi 的對稱點 j ，其值為 j= 2*Mi-i 。因，點 j 、i 在以Mi 為中心的最大回文串的范圍內（[L ,R]），

? ? ? ?a）那么如果P[j] <R-i?（同樣是L和j 之間的距離），說明，以點 j 為中心的回文串沒有超出范圍[L ,R]，由回文串的特性可知，從左右兩端向Mi遍歷，兩端對應的字符都是相等的。所以P[ j ]=P[ i ]（這里得先從點j轉到點i 的情況），如下圖：

?

? ? ?b)如果P[ j ]>=R-i?（即?j 為中心的回文串的最左端超過 L），如下圖所示。即，以點 j為中心的最大回文串的范圍已經超出了范圍[L ,R] ，這種情況，等式P[ j ]=P[ i ]還成立嗎？顯然不總是成立的！因，以點 j 為中心的回文串的最左端超過L，那么在[ L, j ]之間的字符肯定能在( j, Mi ]找到相等的，由回文串的特性可知，P[ i ] 至少等于R- i，至于是否大于R-i（圖中紅色的部分），我們還要從R+1開始一一的匹配，直達失配為止，從而更新R和對應的Mi以及P[ i ]。

? 2）當 i > R時，如下圖。這種情況，沒法利用到回文串的特性，只能老老實實的一步步去匹配。

C++版本一

?

string Manacher(string s) {/*改造字符串*/string res="$#";for(int i=0;i<s.size();++i){res+=s[i];res+="#";}/*數組*/vector<int> P(res.size(),0);int mi=0,right=0; //mi為最大回文串對應的中心點，right為該回文串能達到的最右端的值int maxLen=0,maxPoint=0; //maxLen為最大回文串的長度，maxPoint為記錄中心點for(int i=1;i<res.size();++i){P[i]=right>i ?min(P[2*mi-i],right-i):1; //關鍵句，文中對這句以詳細講解while(res[i+P[i]]==res[i-P[i]])++P[i];if(right<i+P[i]) //超過之前的最右端，則改變中心點和對應的最右端{right=i+P[i];mi=i;}if(maxLen<P[i]) //更新最大回文串的長度，并記下此時的點{maxLen=P[i];maxPoint=i;}}return s.substr((maxPoint-maxLen)/2,maxLen-1); }

JAVA版本一

public String longestPalindrome(String s) {List<Character> s_new = new ArrayList<>();for(int i = 0;i < s.length();i++){s_new.add('#');s_new.add(s.charAt(i));}s_new.add('#');List<Integer> Len = new ArrayList<>();String sub = "";//最長回文子串int sub_midd = 0;//表示在i之前所得到的Len數組中的最大值所在位置int sub_side = 0;//表示以sub_midd為中心的最長回文子串的最右端在S_new中的位置Len.add(1);for(int i = 1;i < s_new.size();i++){if(i < sub_side) {//i < sub_side時，在Len[j]和sub_side - i中取最小值，省去了j的判斷int j = 2 * sub_midd - i;if(j >= 2 * sub_midd - sub_side &&? Len.get(j) <= sub_side - i){Len.add(Len.get(j));}elseLen.add(sub_side - i + 1);}else//i >= sub_side時，從頭開始匹配Len.add(1);while( (i - Len.get(i) >= 0 && i + Len.get(i) < s_new.size()) && (s_new.get(i - Len.get(i)) == s_new.get(i + Len.get(i))))Len.set(i,Len.get(i) + 1);//s_new[i]兩端開始擴展匹配，直到匹配失敗時停止if(Len.get(i) >= Len.get(sub_midd)){//匹配的新回文子串長度大于原有的長度sub_side = Len.get(i) + i - 1;sub_midd = i;}}sub = s.substring((2*sub_midd - sub_side)/2,sub_side /2);//在s中找到最長回文子串的位置return sub;}

三、例題

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110（題解：https://blog.csdn.net/weixin_43272781/article/details/89645047）

四、參考文章

https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin

https://blog.csdn.net/it_liy/article/details/78680786

https://blog.csdn.net/qq_32354501/article/details/80084325

https://www.cnblogs.com/love-yh/p/7072161.html

https://www.cnblogs.com/mini-coconut/p/9074315.html

https://www.cnblogs.com/ysw-go/p/5873350.html

總結

以上是生活随笔為你收集整理的回文字符串(Palindromic_String)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。