wio-
#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 main(void)
{
string str,result;
cin>>str;
getMin(str,result);
cout<<result<<endl;
}
北境漫步-
#include <stdio.h>
#include <string.h>
#define N 50//5000
//插入排序
void insertSort(char* arr,long len)
{
long i=0,j=0;
char tmp;
for(i=1;i<len;i++)
{
for(j=i,tmp=arr[j]; tmp<arr[j-1]&&j>0; j--)
{
arr[j]=arr[j-1];
}
arr[j]=tmp;
}
}
void delRepeat(char *arr,long len)
{
int i,j;
for(i=1;i<len;i++)
{
if(arr[i]==arr[i-1])
{
for(j=i; j<len; j++)
{
arr[j-1]=arr[j];
}
arr[len-1]=0;
len--;
i--;
}
}
}
void show(char *arr,long len)
{
if(len==1)
{
printf("%c",arr[0]);
}
else if(len>1)
{
printf("%c",arr[len-1]);
show(arr,len-1);
printf("%c",arr[len-1]);
}
}
main()
{
char str[N+1]={0};
int len;
printf("请输入：");
scanf("%s",str);
len=strlen(str);
insertSort(str,len);
//puts(str);
delRepeat(str,len);
//puts(str);
show(str,len);
printf(" ");
getchar();
}
康康map-
有趣，关注中.
高金山,你的错了,要求是"给S添加尽量少的字符",但你的不符合,例子:
请输入：fesse
sfefs
向上面那个只要在最右边加个"f"就行了fessef.
tanyuguo,建议你将main函数改为int返回类型，并返回0.这样大多数编译器都能通过，如果void的话，至少gcc不能通过编译.
苏州马小云-
...先对字符串的每一个字符向前和向后比较，找到最大的回文子串，然后再添加
真可-
c的:
#include <stdio.h>
#include <string.h>
#include <malloc.h>
main()
{
char S[256],*p1,*p2;int len,mid=-1,st=0,ed=0,t_st,t_ed,i,j,t_i,p2i=0;
scanf("%255[^ ]",S);
len=strlen(S);
//求最大回文,在源串中,以下标st开始,ed结束
while(++mid<len-1)
{
if(S[mid]==S[mid+1])
{t_st=mid-1,t_ed=mid+2;
while(t_st>-1&&t_ed<len&&S[t_st]==S[t_ed])t_st--,t_ed++;
if(ed-st<--t_ed-++t_st)ed=t_ed,st=t_st;
}
t_st=mid-1,t_ed=mid+1;
while(t_st>-1&&t_ed<len&&S[t_st]==S[t_ed])t_st--,t_ed++;
if(ed-st<--t_ed-++t_st)ed=t_ed,st=t_st;
}
//p1中放置源串中回文前的部分,p2放置回文前后部合并的部分
p1=(char*)malloc(st+1);
p2=(char*)malloc(len-ed+st);
for(i=0;i<st;p1[i]=S[st-1-i],i++);
p1[i]=0;
i=0,j=ed+1;
while(j<len)
{
for(t_i=i;t_i<st;t_i++)
if(p1[t_i]==S[j])
{while(i<t_i)p2[p2i++]=p1[i++];i++;break;}
p2[p2i++]=S[j++];
}
p2[p2i]=0;
strcat(p2,p1+i);
//逆序输出合并部分
for(i=len-ed+st-2;i>-1;i--)putchar(p2[i]);
//输出回文
for(i=st;i<ed+1;i++)putchar(S[i]);
//输出合并部分
puts(p2);
free(p1);
free(p2);
}
c++的:效率不用说,比c低N多
#include <string>
#include <iostream>
#include <limits>
using namespace std;
main()
{
string A;
cin >>A;
int min_len=INT_MAX;
string O;
bool flag;
for(int mid=0;mid<A.size()+1;mid++)
{
bool tflag=0;
//将源串选一个中点,拆分成两个串,然后将两个串合成一个最小串
string frt(A.begin(),A.begin()+mid),bck(A.begin()+mid,A.end());
frt.assign(frt.rbegin(),frt.rend());
//判定是奇/偶对称
if(frt[0]==bck[0])
{
int i=0,j=0;
while(frt[i]==frt[i+1])i++;
while(bck[j]==bck[j+1])j++;
if(i==j)tflag=1;
}
//合并串
int pbck=0;
while(pbck<bck.size())
{
int n;
if((n=frt.find_first_of(bck[pbck],0))!=-1)
{
bck.insert(pbck,frt,0,n);
pbck+=n;
frt.erase(0,n+1);
}
pbck++;
}
bck+=frt;
//如果是最短串,保存
if(bck.size()<min_len)O=bck,min_len=bck.size(),flag=tflag;
}
for(int i=O.size()-1;i>0;i--)cout <<O[i];
//根据奇偶对称来决定输出中点次数
if(flag)cout <<O[0];
cout <<O;
system("pause");
}
里论外几-
真的是很难哦～～
ardim-
总要指定一个基准位吧?
不然5000个字符从2500的那个开始?
左迁-
很复杂的算法问题~
瑞瑞爱吃桃-
是呀 我不知道你说的是什么呀
我不懂运营-
what is the 回文字符串?