社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
给出一个字符串S,求S的最长回文子串的长度。
样例:字符串“PATZJUJZTACCBCC”的回文子串为“ATZJUJZTA”,长度为9。
如果使用暴力解法,枚举子串的两个端点i和j,时间复杂度需要O(n^2)。判断子串是否为回文需要O(n),总体时间复杂度为O(n^3),使用动态规划可以达到最优的O(n^2),而使用动态规划解决最长回文子串的方法有很多种,下面讨论最简单的一种方法。
令dp[i][j]表示S[i]至S[j]所表示的子串是否为回文子串,是则为1,不是为0。如此根据S[i]是否等于S[j],可以把问题分为两类:
(1)S[i]==S[j],那么只要S[i+1]至S[j-1]是回文子串,S[i]至S[j]就是回文子串;如果S[i+1]至S[j-1]是不是回文子串,则S[i]至S[j]也不是回文子串。
(2)S[i]!=S[j],那么S[i]至S[j]一定不是回文子串。
由此可以 写出其状态转移方程:
边界:dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1]?0:1) ps:这里的dp初始化记录了长度为1和2的回文子串
但是这里还存在一个问题,就是在求dp[i][j]时,无法保证dp[i+1][j-1]已经被计算了,比如先固定i=0,然后j从2开始枚举。当求解dp[0][2]时,的dp[1][1]已经在初始中得到;当求解dp[0][3]时,会转换求dp[1][2],而dp[1][2]也在初始化是获得了;当求解dp[0][4]是,转换求解dp[1][3],但dp[1][3]之前却没有被计算出来,因此无法转移状态。
根据上面的公式,边界表示的是长度为1和2的回文子串,且每次转移时都说对子串的长度减1。因此不妨按照子串的长度和子串的初始位置进行枚举,即第一次可以枚举长度为3的子串的dp值,第二次在第一次的基础上枚举长度为4的子串的dp值....直到枚举到原字符串的长度。长度为3的示意图如下:
根据上面的分析,可以给出下面的代码:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int M=1010;
int dp[M][M];
int main(){
int i,j,k,s,e,ans=1;
string str;
cin>>str;
int len=str.length();
for(i=0;i<len;i++){
dp[i][i]=1;
if(str[i]==str[i+1]){
dp[i][i+1]=1;
ans=2;
}
}
for(k=3;k<=len;k++){ //子串的长度
for(i=0;i+k-1<len;i++){ //子串左端点
j=i+k-1; //子串右端点
if(str[i]==str[j]&&dp[i+1][j-1]){
dp[i][j]=1;
ans=k;
s=i;e=j; //保存最长回文子串的下标
}
}
}
for(i=s;i<=e;i++){
cout<<str[i];
}
cout<<endl<<ans<<endl;
}
下面具体看一个题目:
题目描述
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同。如abba和yyxyy。在判断回文时,应该忽略所有标点符号和空格,且忽略大小写,但输出应保持原样(在回文串的首部和尾部不要输出多余字符)。输入字符串长度不超过5000,且占据单独的一行。应该输出最长的回文串,如果有多个,输出起始位置最靠左的。
输入
一行字符串,字符串长度不超过5000。
输出
字符串中的最长回文子串。
样例输入
Confuciuss say:Madam,I'm Adam.
样例输出
Madam,I'm Adam
这个题目完全可以使用上面的思路来求解,需要注意的是:上面的方法是求最右端的子串,而题目要求是最左端的子串。解决方法也很容易,从字符串的末端开始枚举即可:
#include <cstdio>
#include <cstring>
using namespace std;
const int M=5002;
int dp[M][M];
int pos[M]; //保存新位置到原位置的映射
bool isAlptha(char c){
return 'a'<=c && c<='z' || 'A'<=c && c<='Z';
}
bool isDigit(char c){
return '0'<=c && c<='9';
}
char* toUpper(char* v){
for(int i=0;v[i];i++){
if('a'<=v[i] && v[i]<='z'){
v[i]-=32;
}
}
return v;
}
int main(){
int i,j,k,s,e,ans=1,c=0;
char* str1=new char[M];
char* str=new char[M];
gets(str1);
for(i=0;str1[i];i++){
if(isAlptha(str1[i])||isDigit(str1[i])){
str[c]=str1[i];
pos[c++]=i; //保存新位置到原位置的映射
}
}
str=toUpper(str);
int len=strlen(str);
for(i=0;i<len;i++){
dp[i][i]=1;
if(str[i]==str[i+1]){
dp[i][i+1]=1;
ans=2;
}
}
for(k=3;k<=len;k++){ //子串的长度
for(j=len-1;j-k+1>=0;j--){ //子串右端点
i=j-k+1; //子串左端点
if(str[i]==str[j]&&dp[i+1][j-1]){
dp[i][j]=1;
ans=k;
s=i;e=j;
}
}
}
s=pos[s]; e=pos[e];
for(i=s;i<=e;i++){
printf("%c",str1[i]);
}
printf("n");
}
题目来源:http://www.codeup.cn/problem.php?cid=100000629&pid=0
另外关于O(n)的回文算法Manacher,可以参考:
https://segmentfault.com/a/1190000008484167?utm_source=tag-newest
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!