回文的一个问题 - C语言论坛

问题点数：0 回复次数：5

回文的一个问题

今天在看飞燕之家的一个问题，原帖在这http://
问题描述：
所谓回文，就是像"acbca"或者"12966921"这样的字符串，左右对称。
现在的问题是，假如给你"abaqbaa"这样的字符串，你可以对它添加一
些字符，得到"aabaqqabaa"变成回文，一共加了3个字符。
问对于随意给的一字字符串，你最少要加多少个字符才能使它变成回文？
对于刚刚的"abaqbaa"，其实可以只加2个字符变成"aabaqabaa"就成为回
文了，2就是这个字符串的最少添加字符数目。

输入
多组测试数据，每组只有一行，就是一个字符串，串长小于1000

输出
输出最少要加的字符个数

样例输入
abaqbaab
abccba
1357351

样例输出
3
0
2
想了很久没做出来，看看答案还没看懂，

下面贴着的是 ttuurr的答案
谁大概能解释一下，给点思路就好，谢谢了

程序代码：

#include <cstdio>
#include <cstring>
const int MAX=1000;
char s[MAX+1];
int c[2][MAX+1]; 
int main() {
    int i, j, len;
    
    while(scanf("%s", s) != EOF) {
        len=strlen(s);
        for(i=1; i<=len; i++) 
    { 
            for(j=0; j<=len; j++)           
              c[0][j]=c[1][j]; 
        
            for(j=1; j<=len; j++) 
        {                
        c[1][j]=c[1][j-1];     
                if(c[0][j] > c[1][j])
                    c[1][j]=c[0][j];
                if(s[i-1]==s[len-j] && c[1][j]<c[0][j-1]+1) 
                    c[1][j]=c[0][j-1]+1;
            }
        }
        
        printf("%d\n",len-c[1][len]);
        for(i=0; i<=len; i++)
            c[1][i]=0;
    }
    return 0;
}

[[it] 本帖最后由 xuanzilie 于 2008-7-22 22:41 编辑 [/it]]

搜索更多相关主题的帖子: 回文　

第 2 楼

得分:0

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include <iostream>
#include <string>
using namespace std;
const int MAX=1005;
const int M=2;
double _L[M][MAX];
struct{
    double* operator [](int i){
        return _L[i%M];
    }
}L;
int main(){
    string strA;
    while(cin>>strA)
    {
        string strB;
        strB.assign(strA.rbegin(),strA.rend());
        int i,j,aLen,bLen;
        aLen=bLen=strA.length();
        for(i=0;i<=aLen;++i)
            L[i][0]=L[0][i]=0;
        for(i=1;i<=aLen;++i)
            for(j=1;j<=bLen;++j)
                if(strA[i-1]==strB[j-1])
                    L[i][j]=L[i-1][j-1]+1;
                else
                    L[i][j]=L[i-1][j]>L[i][j-1]?L[i-1][j]:L[i][j-1];
        cout<<aLen-L[aLen][aLen]<<endl;
        for(i=0;i<=aLen;++i)
            memset(L[i],0,sizeof(int)*(aLen+1));
    }
    return 0;
}

贴个我写的
dp..！
看我签名！

[[it] 本帖最后由菜鸟选手于 2008-7-23 00:18 编辑 [/it]]