[搜狗]求一个字符串的最小回文划分


给定一个字符串,求它的最小回文划分。
比如abaccdd,那么他的最小划分为aba|cc|dd。
已邀请:

sjf0115 - Stay Hungry, Stay Foolish

赞同来自: zack6514


思路:

基于“最长回文子串算法”求出当前字符串的最长回文子串,就可以分成3部分
a、最长回文子串left部分
b、最长回文子串
c、最长回文子串right部分

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

代码:
    /*-------------------------------------
    *   日期:2015-02-08
    *   作者:SJF0115
    *   题目: 字符串回文分割
    *   来源:网易
    *   博客:http://blog.csdn.net/sunnyyoona/article/details/40376875
    ------------------------------------*/
    #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="abaccdd";
        int beg = 0;
        int end = str.length()-1;
        SpilitPalindromeNumber(str,beg,end);
        return 0;
    }

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~