c說話輸入字符串中最年夜對稱子串長度的3種處理計劃。本站提示廣大學習愛好者：（c說話輸入字符串中最年夜對稱子串長度的3種處理計劃）文章只能為提供參考，不一定能成為您想要的結果。以下是c說話輸入字符串中最年夜對稱子串長度的3種處理計劃正文
成績描寫：
輸出一個字符串，輸入該字符串中最年夜對稱子串的長度。例如輸出字符串：“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有關;
綜上剖析代碼以下：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
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;
}
輸入成果：
xu@xu-ThinkPad-X61:~/algorithm$ gcc LongSunmetricSub.c
xu@xu-ThinkPad-X61:~/algorithm$ ./a.out
----- is:1
----- is:3
----- is:1
----- is:2
----- is:3
----- is:1
----- is:1
----- is:1
----- is:1
----- is:1
----- is:1
----- is:3
----- is:1
----- is:1
----- is:1
max length is:3
