背景：

所謂對(duì)稱子字符串，就是這個(gè)子字符串要么是以其中一個(gè)詞對(duì)稱：比如 “aba”， “abcba”；要么就完全對(duì)稱：比如"abba", "abccba"。

問(wèn)題：

給你一個(gè)字符串，找出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。

思路：

首先，我們用字符數(shù)組 char[] array 來(lái)保持這個(gè)字符串，假設(shè)現(xiàn)在已經(jīng)遍歷到第 i 個(gè)字符，要找出以該字符為“中心”的最長(zhǎng)對(duì)稱字符串，我們需要用另兩個(gè)指針?lè)謩e向前和向后移動(dòng)，直到指針到達(dá)字符串兩端或者兩個(gè)指針?biāo)傅淖址幌嗟取Ｒ驗(yàn)閷?duì)稱子字符串有兩種情況，所以需要寫出兩種情況下的代碼：

1. 第 i 個(gè)字符是該對(duì)稱字符串的真正的中心，也就是說(shuō)該對(duì)稱字符串以第 i 個(gè)字符對(duì)稱， 比如： “aba”。代碼里用 index 來(lái)代表 i.

[java] view plaincopy public?static?int?maxLengthMiddle(char[]?array,?int?index)?{??????int?length?=?1;?//最長(zhǎng)的子字符串長(zhǎng)度??????int?j?=?1;?//前后移動(dòng)的指針??????while?((array[index?-?j]?==?array[index?+?j])?&&?(index?-?j)?>=?0?&&?array.length?>?(index?+?j))?{??????????length?+=?2;??????????j++;??????}????????????return?length;??}??

2. 第 i 個(gè)字符串是對(duì)稱字符串的其中一個(gè)中心。比如“abba”。

[java] view plaincopy public?static?int?maxLengthMirror(char[]?array,?int?index)?{??????int?length?=?0;?//最長(zhǎng)的子字符串長(zhǎng)度??????int?j?=?0;?//前后移動(dòng)的指針??????while?((array[index?-?j]?==?array[index?+?j?+?1])?&&?(index?-?j)?>=?0?&&?array.length?>?(index?+?j?+?1)){??????????length?+=?2;??????????j++;??????}????????????return?length;??}??

有了這樣兩個(gè)函數(shù)，我們只需要遍歷字符串里所有的字符，就可以找出最大長(zhǎng)度的對(duì)稱子字符串了。

[java] view plaincopy public?static?int?palindrain(char[]?array)?{??????if?(array.length?==?0)?return?0;??????int?maxLength?=?0;??????for?(int?i?=?0;?i?<?array.length;?i++)?{??????????int?tempMaxLength?=?-?1;??????????int?length1?=?maxLengthMiddle(array,?i);??????????int?length2?=?maxLengthMirror(array,?i);??????????tempMaxLength?=?(length1?>?length2)???length1?:?length2;??????????if?(tempMaxLength?>?maxLength)?{??????????????maxLength?=?tempMaxLength;??????????}??????}??????return?maxLength;??}?? 因?yàn)檎页鲆缘?i 個(gè)字符為“中心”對(duì)稱字符串復(fù)雜度為 O（N），所以整個(gè)算法的復(fù)雜度為O（N^2）。

另一種方法是把原始字符串反轉(zhuǎn)，這樣最長(zhǎng)對(duì)稱子字符串問(wèn)題可以轉(zhuǎn)化成求兩個(gè)字符串的最長(zhǎng)公共子字符串問(wèn)題（備注：不是最長(zhǎng)公共子序列）。

有一種可以把復(fù)雜度降到O（N）的算法，但是這個(gè)算法要利用 suffix tree， 有興趣的可以搜索一下。