問(wèn)題描述：

輸入一個(gè)字符串，輸出該字符串中最大對(duì)稱子串的長(zhǎng)度。例如輸入字符串：“avvbeeb”，該字符串中最長(zhǎng)的子字符串是“beeb”，長(zhǎng)度為4，因而輸出為4。

解決方法：中序遍歷

一，全遍歷的方法：

1.全遍歷的方法，復(fù)雜度O（n3）;

2.遍歷原字符串的所有子串，然后判斷每個(gè)子串是否對(duì)稱；

實(shí)現(xiàn)方法是：我們讓一個(gè)指針i從頭至尾遍歷，我們用另一個(gè)指針j從j=i+1逐一指向i后面的所有字符。就實(shí)現(xiàn)了原串的所有子串的遍歷（子串為指針i到j(luò)中間的部分）;
最后判斷得到的子串是否對(duì)稱即可;

二，此外還有個(gè)巧妙的方法，值得和大家分享一下（這是自己想的哦，轉(zhuǎn)載請(qǐng)注明出處）：

原串是str1=“avvbeeb”，將其翻轉(zhuǎn)得到str2=“beebvva”，然后錯(cuò)位比較：

1：               avvbeeb

str2：beebvva             （上下對(duì)齊的元素是a;a比較）

2：              avvbeeb

str2：beebvva           （上下對(duì)齊的量元素av;va比較，不對(duì)稱）

…………

11：              avvbeeb

str2：                  beebvva           （上下對(duì)齊的量元素beeb;beeb比較，得到最長(zhǎng)對(duì)稱子串）

…………

該方法要移動(dòng)m+n次，每次元素比較個(gè)數(shù)從1到m不等，復(fù)雜度O（n2）;

三，最值得推薦的還是下面的方法，復(fù)雜度O（n）：

（以下都是自己想的自己寫(xiě)的，碼字實(shí)在辛苦，轉(zhuǎn)載請(qǐng)注明出處）

1.起始這道題分析起來(lái)非常扯淡，花了我兩天的空閑時(shí)間才搞定！

2.分析過(guò)程如下：

3. 1-k位的元素中，其中最長(zhǎng)對(duì)稱子串（包含第k位元素）長(zhǎng)度為f（n），我們討論f（n+1）與f（n）的關(guān)系;

4.比如 b xxx a其中xxx代表對(duì)稱子串，a為第n+1位元素，我們現(xiàn)在求f（n+1）;

5.我們分析所有情況：（我們用xxx代表n位對(duì)稱子串）

          數(shù)組A存放字符數(shù)組;

          f（n）表示f（n）位元素對(duì)應(yīng)子串長(zhǎng)度;

   分析如下A[n+1]=a的子串長(zhǎng)度值f（n+1）值是多少：

   1：bxxxa  ：A[n+1]位元素a與對(duì)稱子xxx串前的一位元素b不同時(shí);

     1.1: a與左相鄰元素不同，即xxx=bxb時(shí)，bbxba不是對(duì)稱子串，f（n+1）=1;

     1.2: a與左相鄰元素相同，即xxx=axa時(shí)，baxaa，如果是對(duì)稱子串，則x這個(gè)未知部分必須全部是a，即

            baaaa，f（n+1）=f（n）+1，否則不是對(duì)稱子串f（n+1）=1;

   axxxa  ：A[n+1]位元素a與對(duì)稱子串前一位元素相同;

     2.這種情況f（n+1）位元素a與其左相鄰元素是否相同都不影響f（n+1）的結(jié)果，

        比如：a bacab a        a aaaaa a

        串長(zhǎng)：1 13135 7        1 23456 7        也就是xxx不論是何種情況的對(duì)稱串，f（n+1）=f（n）+2;

 6.綜上分析，串A[n+1]位的值f（n+1）只和串中第A[n]位字符以及第A[n-f（n）-1]有關(guān);

    （5中分析的f（n+1）=1的情況可以忽略不考慮，因?yàn)樽钚?duì)稱子串值>=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

      此時(shí)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

      此時(shí)f（n+1）與它前面有幾個(gè)a有關(guān);

綜上分析代碼如下：

輸出結(jié)果：