字符串水题

字符串水题

题意：给定一个字符串str，要求你只能在字符串的头部或尾部添加任意字符，使得最后的字符串是一个回文字符串并且满足字符串的长度最短，问最少需要添加几个字符。

分析：首先先看一下，什么是回文？回文有两种形式，(1)是xxxcxxx，(2)是xxxccxxx。分别表示的是长度为奇数和偶数的回文串

对于一个长度为len的字符串，要求你只能在字符串的头部或尾部添加任意字符使之成为回文字符串的话。那么最坏的情况“是把第一个字符或最后一个字符做为中间字符，添加剩下的len-1个字符到另一边，并且最后的得到的回文串长度为奇数”，比如给定一个字符串“adah”，那么最坏的情况就是“hadadah”或“adahada”

但是我们发现这个情况是错的，因为我们忽略了最好的情况。一个字符串可能本来就是一个回文串，比如“aba”，那么分析题目我们可以得到结论

给定一个长度为len的字符串，只能在字符串的头部或尾部添加任意字符使之成为回文字符串的话。需要添加的字符数量是0~(len-1)

那么我们只要分别对头部和尾部进行枚举0~(len-1)，然后找到最少的添加的个数就是答案

代码

/*
Author: chenguolin
Date: 2014-03-05
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

// 判断是否是回文
bool isOk(char *str){
    int len = strlen(str);
    int i = 0, j = len-1;
    while(i < j){
      if(str[i] != str[j])
          return false;
      i++, j--;
    }
    return true;
}

// 加在头部
int getHead(char *str){
    int len = strlen(str);
    // 枚举添加0~len-1个字符
    for(int i = 0; i < len; i++){
      char tmpStr[MAXN];
      int pos = 0, j = len-1;
      while(pos < i){
          tmpStr[pos++] = str[j--];
      } 
      strcat(tmpStr, str);   
      if(isOk(tmpStr))
          return i;
    }
}

// 加在尾部
int getTail(char *str){
    int len = strlen(str);
    // 枚举添加0~len-1个字符
    for(int i = 0; i < len; i++){
        char tmpStr[MAXN];
        memcpy(tmpStr, str, sizeof(str));
        int pos = len, j = 0;
        while(j < i){
            tmpStr[pos++] =  str[j++];
        }
        tmpStr[pos] = '\0';
        if(isOk(tmpStr))
          return i;
    }
}

int main(){
    char str[MAXN];
    scanf("输入一个字符串：%s", str);
    int head = getHead(str); // 得到在头部添加字符需要几个
    int tail = getTail(str); // 得到在尾部添加字符需要几个
    printf("最少需要添加：%d\n", min(head, tail));
}

这个代码没有经过编译和测试，是lz临时想到就写得，欢迎广大博友来拍砖。