[网易]字符串回文分割

2019-11-06 08:40:50

字体：大中小

来源：转载

供稿：网友

转载链接： http://blog.csdn.net/SunnyYoona/article/details/40376875

【题目】将一个很长的字符串，分割成一段一段的子字符串，子字符串都是回文字符串。有回文字符串就输出最长的，没有回文就输出一个一个的字符。例如：habbafgh 输出h,abba,f,g,h。【思路一】基于“最长回文子串算法”求出当前字符串的最长回文子串，就可以分成3部分 a、最长回文子串left部分 b、最长回文子串 c、最长回文子串right部分

然后分别求a和c的最长回文子串递归至每部分都成单个字符+当前最长回文子串，就可以分解成最终结果。

【代码一】

#include<string> #include<iostream> using namespace std; // beg end 用于返回最大回文串的范围 void MaxPalindromeNumber(string str,int& beg,int& end){ int maxLen = 1,start = beg; int left,right; for(int i = beg;i <= end;i++){ //奇数字串 int oddLen = 1; left = i-1; right = i+1; while(left >= beg && right <= end && 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 >= beg && right <= end && str[left] == str[right]){ left--; right++; evenLen += 2; } //更新最大长度 if(evenLen > maxLen){ maxLen = evenLen; //记录当前最大回文串的起始位置 start = left+1; } } beg = start; end = start + maxLen - 1; } int index = 0; void SpilitPalindromeNumber(string str,int& beg,int& end){ int lbeg = beg; int rend = end; //beg end 返回当前最大回文串的起始点和截止点 MaxPalindromeNumber(str,beg,end); int lend = beg - 1; int rbeg = end + 1; // lbeg lend 最大回文串的左部 // rbeg rend 最大回文串的右部 if(lbeg <= lend){ SpilitPalindromeNumber(str,lbeg,lend); } //控制格式输出 if(index == 0){ cout<<str.substr(beg,end-beg+1); index++; } else{ cout<<","<<str.substr(beg,end-beg+1); index++; } if(rbeg <= rend){ SpilitPalindromeNumber(str,rbeg,rend); } } int main(){ string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw"; int beg = 0; int end = str.length()-1; SpilitPalindromeNumber(str,beg,end); return 0; }

【思路二】先将给定字符串翻转,然后和原来的字符串一起，这样就变成了最长公共子序列问题。此时可以利用动态规划的思路来完成。关于最长公共子序列问题可以参考<算法导论>里面有详细的说明

上一篇：HDU 5305

下一篇：11、进程控制