怎样生成回文字符串

来源：百度知道 编辑：UC知道 时间：2024/09/18 05:15:52
给出一个长度不超过5000的字符串S，给S添加尽量少的字符，使它变成一个回文字符串。
示例：
输入：cbabd
输出：dcbabcd //串首字符前加入d，串尾字符前加入c
这道题我也知道有些难！！哈哈，不难就不问了！！
思路的确是先找到最大回文子串，但是添加的算法很难实现啊！！

#include <iostream>
#include <string>
using namespace std;

#define N 80

bool isHuiWen(string str)
{
int i;
for(i=0;i<str.length()-1-i;i++)
if(str[i]!=str[str.length()-1-i])
return 0;
return 1;
}

int getMin(string src,string &dest)
{
if(isHuiWen(src))
{
dest=src;
return 0;
}

char p[N];
int top=0;

string temp=src;
string tempL,tempR;
int m1,m2;

while(temp[0]==temp[temp.length()-1])
{
p[top++]=temp[0];
temp=temp.substr(1,temp.length()-2);
}

m1=getMin(temp[temp.length()-1]+temp,tempL);
m2=getMin(temp+temp[0],tempR);
if(m1<m2) dest=tempL;
else dest=tempR;

while(top>0)
{
top--;
dest=p[top]+dest;
dest+=p[top];
}

return dest.length()-src.length();
}

void m