字符串水題

題意：給定一個字符串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臨時想到就寫得，歡迎廣大博友來拍磚。