回文字符串(Palindromic_String)

一、基本概念

回文字符串：是一个正读和反读都一样的字符串。

二、问题与算法

（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

#include

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--;

}

else

return 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

for(int j=i+1;j

{

int temp1,temp2;

for(temp1=i,temp2=j;temp1

{

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 ++;

}

else

break;

}

}

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 here

O(n^2)

int len = s.size();

memset(dp, 0, sizeof(dp));

for(int i=0; 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

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

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]

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

{

res+=s[i];

res+="#";

}

/*数组*/

vector P(res.size(),0);

int mi=0,right=0; //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值

int maxLen=0,maxPoint=0; //maxLen为最大回文串的长度，maxPoint为记录中心点

for(int i=1;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

{

right=i+P[i];

mi=i;

}

if(maxLen

{

maxLen=P[i];

maxPoint=i;

}

}

return s.substr((maxPoint-maxLen)/2,maxLen-1);

}

JAVA版本一

public String longestPalindrome(String s) {

List 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 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));

}

else

Len.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