Question

c/c++回文词问题

回文词是一种对称的字符串，即从左到右读和从右到左读的结果一样。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。请编写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。
[输入数据]
输入数据的第一行包含一个整数N，表示给定字符串的长度（3～5000）。
第二行是一个长度为N的字符串，它由大写字母，小写字母和数字组成。大小写被认为不同。
[输出数据]
输出一个整数，表示需要插入的最少字符数。并输出一个插入后的示例。
是要用c/++实现，另外看清楚是要输出插入后的序列！题目不怎么难，但我没时间了，代码中文注释越多越好，如果实现的好联系我我会有追加奖励！也可加我扣思思伞要玲玲久要领

Answer 1

#include <string>

// 定义函数的返回值类型
typedef std::pair<std::string, std::string::size_type> result_type;
// 使用递归来解决，因为如果一个串是回文，那么去掉头尾两个字符，它依然是回文
result_type hui_wen(std::string str){
    result_type res;
    if (str.size() < 2){// 字符串长度小于2，已经是回文
        res.first = str;
        res.second = 0;
    }
    else{
        char const a = str.front(), b = str.back();
        if (a == b){// 头尾两个字符相同，考虑除去这两个字符的子串
            result_type tmp = hui_wen(str.substr(1, str.size() - 2));
            res.first = a + tmp.first + b;
            res.second = tmp.second;
        }
        else{
            // 分别考虑在前面插入b和后面插入a，看哪一种方案更好
            result_type tmp1 = hui_wen(str.substr(1)), tmp2 = hui_wen(str.substr(0, str.size() - 1));
            if (tmp1.second < tmp2.second){
                res.first = a + tmp1.first + a;
                res.second = tmp1.second + 1;
            }
            else{
                res.first = b + tmp2.first + b;
                res.second = tmp2.second + 1;
            }
        }
    }

    return res;
}

#include <fstream>
#include <iostream>
int main(){
    std::string::size_type s;// 因为使用的string类型，这个变量没用
    std::string str;

    std::ifstream istr("input.txt");// 从input.txt中读入数据，根据需要自己修改
    if (istr >> s >> str){
        result_type tmp = hui_wen(str);
        std::ofstream ostr("output.txt");// 输出到output.txt中
        ostr << tmp.second << "\n" << tmp.first;
    }
    else{
        std::cerr << "input error\n";
        return __LINE__;
    }

    return 0;
}

追问

试了一下；front()back()这里报错；好吧 环境是 vc60 原谅我菜 是什么原因呢

追答

正如zhaoyj163em所说，上面的复杂度是指数级别的，这意味着n较大时，程序是不可行的。

附件是根据算法导论得到的新程序，不过注释就不太好写了，想了解的话还是看书吧。