輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。
要判斷一個字符串是不是對稱的，不是一件很難的事情。我們可以先得到字符串首尾兩個字符，判斷是不是相等。如果不相等，那該字符串肯定不是對稱的。否則我們接著判斷里面的兩個字符是不是相等，以此類推。基于這個思路，我們不難寫出如下代碼：
////////////////////////////////////////////////////////////////
// Whether a string between pBegin and pEnd is symmetrical?
////////////////////////////////////////////////////////////////
bool?IsSymmetrical(char* pBegin,?char* pEnd)
{
???????if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
??????????????return?false;
?
???????while(pBegin < pEnd)
???????{
??????????????if(*pBegin != *pEnd)
?????????????????????return?false;
?
??????????????pBegin++;
??????????????pEnd --;
???????}
?
???????return?true;
}
要判斷一個字符串pString是不是對稱的，我們只需要調(diào)用IsSymmetrical(pString, &pString[strlen(pString) – 1])就可以了。
現(xiàn)在我們試著來得到對稱子字符串的最大長度。最直觀的做法就是得到輸入字符串的所有子字符串，并逐個判斷是不是對稱的。如果一個子字符串是對稱的，我們就得到它的長度。這樣經(jīng)過比較，就能得到最長的對稱子字符串的長度了。于是，我們可以寫出如下代碼：
////////////////////////////////////////////////////////////////
// Get the longest length of its all symmetrical substrings
// Time needed is O(T^3)
////////////////////////////////////////////////////////////////
int?GetLongestSymmetricalLength_1(char* pString)
{
???????if(pString == NULL)
??????????????return?0;
?
???????int?symmeticalLength = 1;
?
???????char* pFirst = pString;
???????int?length = strlen(pString);
???????while(pFirst < &pString[length - 1])
???????{
??????????????char* pLast = pFirst + 1;
??????????????while(pLast <= &pString[length - 1])
??????????????{
?????????????????????if(IsSymmetrical(pFirst, pLast))
?????????????????????{
???????????????????????????int?newLength = pLast - pFirst + 1;
???????????????????????????if(newLength > symmeticalLength)
??????????????????????????????????symmeticalLength = newLength;?????????????????????????
?????????????????????}
?
?????????????????????pLast++;
??????????????}
?
??????????????pFirst++;
???????}
?
???????return?symmeticalLength;
}
我們來分析一下上述方法的時間效率。由于我們需要兩重while循環(huán)，每重循環(huán)需要O（n）的時間。另外，我們在循環(huán)中調(diào)用了IsSymmetrical，每次調(diào)用也需要O（n）的時間。因此整個函數(shù)的時間效率是O（n3）。
通常O（n3）不會是一個高效的算法。如果我們仔細分析上述方法的比較過程，我們就能發(fā)現(xiàn)其中有很多重復(fù)的比較。假設(shè)我們需要判斷一個子字符串具有aAa的形式（A是aAa的子字符串，可能含有多個字符）。我們先把pFirst指向最前面的字符a，把pLast指向最后面的字符a，由于兩個字符相同，我們在IsSymtical函數(shù)內(nèi)部向后移動pFirst，向前移動pLast，以判斷A是不是對稱的。接下來若干步驟之后，由于A也是輸入字符串的一個子字符串，我們需要再一次判斷它是不是對稱的。也就是說，我們重復(fù)多次地在判斷A是不是對稱的。
造成上述重復(fù)比較的根源在于IsSymmetrical的比較是從外向里進行的。在判斷aAa是不是對稱的時候，我們不知道A是不是對稱的，因此需要花費O（n）的時間來判斷。下次我們判斷A是不是對稱的時候，我們?nèi)匀恍枰狾（n）的時間。
如果我們換一種思路，我們從里向外來判斷。也就是我們先判斷子字符串A是不是對稱的。如果A不是對稱的，那么向該子字符串兩端各延長一個字符得到的字符串肯定不是對稱的。如果A對稱，那么我們只需要判斷A兩端延長的一個字符是不是相等的，如果相等，則延長后的字符串是對稱的。因此在知道A是否對稱之后，只需要O（1）的時間就能知道aAa是不是對稱的。
我們可以根據(jù)從里向外比較的思路寫出如下代碼：
////////////////////////////////////////////////////////////////
// Get the longest length of its all symmetrical substrings
// Time needed is O(T^2)
////////////////////////////////////////////////////////////////
int?GetLongestSymmetricalLength_2(char* pString)
{
???????if(pString == NULL)
??????????????return?0;
?
???????int?symmeticalLength = 1;
??????
???????char* pChar = pString;
???????while(*pChar !=?'/0')
???????{
??????????????// Substrings with odd length
??????????????char* pFirst = pChar - 1;
??????????????char* pLast = pChar + 1;
??????????????while(pFirst >= pString && *pLast !=?'/0'?&& *pFirst == *pLast)
??????????????{
?????????????????????pFirst--;
?????????????????????pLast++;
??????????????}
?
??????????????int?newLength = pLast - pFirst - 1;
??????????????if(newLength > symmeticalLength)
?????????????????????symmeticalLength = newLength;
?
??????????????// Substrings with even length
??????????????pFirst = pChar;
??????????????pLast = pChar + 1;
??????????????while(pFirst >= pString && *pLast !=?'/0'?&& *pFirst == *pLast)
??????????????{
?????????????????????pFirst--;
?????????????????????pLast++;
??????????????}
?
??????????????newLength = pLast - pFirst - 1;
??????????????if(newLength > symmeticalLength)
?????????????????????symmeticalLength = newLength;
?
??????????????pChar++;
???????}
?
???????return?symmeticalLength;
}
由于子字符串的長度可能是奇數(shù)也可能是偶數(shù)。長度是奇數(shù)的字符串是從只有一個字符的中心向兩端延長出來，而長度為偶數(shù)的字符串是從一個有兩個字符的中心向兩端延長出來。因此我們的代碼要把這種情況都考慮進去。
在上述代碼中，我們從字符串的每個字符串兩端開始延長，如果當(dāng)前的子字符串是對稱的，再判斷延長之后的字符串是不是對稱的。由于總共有O（n）個字符，每個字符可能延長O（n）次，每次延長時只需要O（1）就能判斷出是不是對稱的，因此整個函數(shù)的時間效率是O（n2）。
下載文檔
