問題描述：
輸入一個字符串，輸出該字符串中最大對稱子串的長度。例如輸入字符串：“avvbeeb”，該字符串中最長的子字符串是“beeb”，長度為4，因而輸出為4。
解決方法：中序遍歷
一，全遍歷的方法：
1.全遍歷的方法，復雜度O（n3）;
2.遍歷原字符串的所有子串，然后判斷每個子串是否對稱；
實現方法是：我們讓一個指針i從頭至尾遍歷，我們用另一個指針j從j=i+1逐一指向i后面的所有字符。就實現了原串的所有子串的遍歷（子串為指針i到j中間的部分）;
最后判斷得到的子串是否對稱即可;
二，此外還有個巧妙的方法，值得和大家分享一下（這是自己想的哦，轉載請注明出處）：
原串是str1=“avvbeeb”，將其翻轉得到str2=“beebvva”，然后錯位比較：
1： avvbeeb
str2：beebvva （上下對齊的元素是a;a比較）
2： avvbeeb
str2：beebvva （上下對齊的量元素av;va比較，不對稱）
…………
11： avvbeeb
str2： beebvva （上下對齊的量元素beeb;beeb比較，得到最長對稱子串）
…………
該方法要移動m+n次，每次元素比較個數從1到m不等，復雜度O（n2）;
三，最值得推薦的還是下面的方法，復雜度O（n）：
（以下都是自己想的自己寫的，碼字實在辛苦，轉載請注明出處）
1.起始這道題分析起來非常扯淡，花了我兩天的空閑時間才搞定！
2.分析過程如下：
3. 1-k位的元素中，其中最長對稱子串（包含第k位元素）長度為f（n），我們討論f（n+1）與f（n）的關系;
4.比如 b xxx a其中xxx代表對稱子串，a為第n+1位元素，我們現在求f（n+1）;
5.我們分析所有情況：（我們用xxx代表n位對稱子串）
數組A存放字符數組;
f（n）表示f（n）位元素對應子串長度;
分析如下A[n+1]=a的子串長度值f（n+1）值是多少：
1：bxxxa ：A[n+1]位元素a與對稱子xxx串前的一位元素b不同時;
1.1: a與左相鄰元素不同，即xxx=bxb時，bbxba不是對稱子串，f（n+1）=1;
1.2: a與左相鄰元素相同，即xxx=axa時，baxaa，如果是對稱子串，則x這個未知部分必須全部是a，即
baaaa，f（n+1）=f（n）+1，否則不是對稱子串f（n+1）=1;
axxxa ：A[n+1]位元素a與對稱子串前一位元素相同;
2.這種情況f（n+1）位元素a與其左相鄰元素是否相同都不影響f（n+1）的結果，
比如：a bacab a a aaaaa a
串長：1 13135 7 1 23456 7 也就是xxx不論是何種情況的對稱串，f（n+1）=f（n）+2;
6.綜上分析，串A[n+1]位的值f（n+1）只和串中第A[n]位字符以及第A[n-f（n）-1]有關;
（5中分析的f（n+1）=1的情況可以忽略不考慮，因為最小對稱子串值>=1)
1: A[n+1]和A[n-f（n）-1]相同;
a xxx x a ：acca aaaa acdca
A[n-f（n）-1] A[n] A[n+1]
f（n） f（n+1） ：1124 1234 11134
此時f（n+1）=f（n）+2;
2: A[n+1]和A[n-f（n）-1]不同;A[n+1]和A[n]相同;
如： b xxx a a ：bcacaa baaaaa
A[n-f（n）-1] A[n] A[n+1] ：111332 112345
此時f（n+1）與它前面有幾個a有關;
綜上分析代碼如下：
int FUN(char *inp){//求最大對稱子串長度
int maxlen = 1;//最大長度
int len=strlen(inp);
int record[len];//存包含該位及前個元素最長對稱子串
record[0]=1;
int i=1;
for(;i<len;i++){
int max =1;
if((i-record[i-1]-1)>=0 && inp[i] == inp[i-record[i-1]-1]){
max = max>(record[i-1] + 2)? max:(record[i-1] +2);
}
int k = 1;
while(inp[i] == inp[i-k]){
k++;
}
max = max>k? max:k;
record[i] = max;
printf("----- is:%d/n",record[i]);
if(record[i]>maxlen) maxlen=record[i];
}
return maxlen;
}
int main(){
char *input="abadddkeipdldlfk";
int retlen = FUN(input);//從前向后遞歸
printf("max length is:%d/n",retlen);
return 0;
}
輸出結果：
新聞熱點
疑難解答
圖片精選
