【题目】
给你一个字符串，找出该字符串中对称的子字符串的最大长度。即求最大回文串。
【思路1】暴力法
即不使用技巧，穷举所有可能。时间复杂度为O(n^3)（时间上最长，不推荐使用），空间复杂度为O(1)。
本思路是从最大长度的字串开始，而不是从最小开始。假如说给定的字符串为len，先遍历长度为len的字串是否为回文串，如果是停止，
如果不是遍历长度为len-1的字串是否是回文串，一次类推。
#include <iostream>
using namespace std;
//是否是回文串
bool IsPalindromeSubNumber(string num){
int len = num.length();
for(int i = 0,j=len-1;i < j;i++,j--){
if(num[i] != num[j]){
return false;
}
}
return true;
}
void MaxSubPalindromeNumber(string num){
bool result;
bool flag = false;
int len = num.length();
//遍历字串的长度
for(int i = len;i > 0;i--){
//遍历字串的起始位置
for(int j = 0;j+i <= len;j++){
result = IsPalindromeSubNumber(num.substr(j,i));
if(result){
flag = true;
cout<<num.substr(j,i)<<endl;
}
}
if(flag){
break;
}
}
}
int main(){
string num = "djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
MaxSubPalindromeNumber(num);
return 0;
}
【思路2】
假设现在已经遍历到第 i 个字符，要找出以该字符为“中心”的最长对称字符串，我们需要用另两个指针分别向前和向后移动，直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况，所以需要写出两种情况下的代码：
（1） 第 i 个字符是该对称字符串的真正的中心，也就是说该对称字符串以第 i 个字符对称， 比如： “aba”
（2）第 i 个字符串是对称字符串的其中一个中心。比如“abba”。
所以遍历到每个字符都要考虑两种情况，它可能是在奇数个回文串中或者是在偶数个回文串中
#include<string>
#include<iostream>
using namespace std;
string MaxPalindromeNumber(string str){
int maxLen = 1,start = 0;
int len = str.length();
string s = str;
int left,right;
for(int i = 0;i < len;i++){
//奇数字串
int oddLen = 1;
left = i-1;
right = i+1;
while(left >= 0 && right < len && str[left] == str[right]){
left--;
right++;
oddLen += 2;
}
//更新最大长度
if(oddLen > maxLen){
maxLen = oddLen;
//记录当前最大回文串的起始位置
start = left+1;
}
//偶数字串
left = i;
right = i+1;
int evenLen = 0;
while(left >= 0 && right < len && str[left] == str[right]){
left--;
right++;
evenLen += 2;
}
//更新最大长度
if(evenLen > maxLen){
maxLen = evenLen;
//记录当前最大回文串的起始位置
start = left+1;
}
}
return str.substr(start,maxLen);
}
int main(){
string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
string s=MaxPalindromeNumber(str);
cout<<s<<endl;
return 0;
}
【思路三】Manacher算法
算法的基本思路是这样的：把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶)，同时为了防止越界，在字符串的首部也加入一个特殊符$，但是与分隔符不同。同时字符串的末尾也加入'\0'。算法的核心：用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1，此时回文字符串就是字符串本身。
示例：原字符串 'abba’，处理后的新串 ' $#a#b#b#a#\0’，得到对应的辅助数组p=[0,1,1,2,1,2,5,2,2,1]。
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
//数据预处理
char* Init(char* s){
int len = strlen(s);
char* str = new char(2*len+4);
str[0] = '$';
int index = 1;
for(int i = 0;i < len;i++){
str[index++] = '#';
str[index++] = s[i];
}
str[index++] = '#';
str[index] = '\0';
return str;
}
char* MaxPalindromeNumber(char* s){
char *str = Init(s);
int maxId = 0,center = 1;
int len = strlen(str);
int *p = new int[len+1];
// MaxId为i字符之前最大回文串向右延伸的最大位置
// id为MaxId对应的最大回文串的中心位置
for(int i = 1;i < len;i++){
//初步定i位置字符为中心的半径
if(maxId > i){
p[i] = min(maxId - i,p[2*center - i]);
}
else{
p[i] = 1;
}
//继续确定i位置字符为中心的半径 这地方用到'$'
while(str[i-p[i]] == str[i+p[i]]){
p[i]++;
}
//更新MaxId,id
if(p[i]+i > maxId){
maxId = p[i] + i;
center = i;
}
}
// 最大长度
int maxLen = 0;
center = 1;
for(int i = 1;i < len;i++){
if(str[i] != '#' && p[i] - 1 > maxLen){
maxLen = p[i] - 1;
center = i;
}
}
//提取最大回文串
char* maxStr = new char[maxLen+1];
int index = 0;
for(int i = center - maxLen;i <= center + maxLen;i++){
if(str[i] != '#'){
maxStr[index++] = str[i];
}
}
maxStr[index] = '\0';
return maxStr;
}
int main(){
char* str="skjflkdsjfkldsababasdlkfjsdwieowowwpw";
cout<<MaxPalindromeNumber(str);
return 0;
}
相关链接：
时间： 2024-10-29 12:34:15