程序员面试100题之一：对称字符串的最大长度
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。
要判斷一個字符串是不是對稱的，不是一件很難的事情。我們可以先得到字符串首尾兩個字符，判斷是不是相等。如果不相等，那該字符串肯定不是對稱的。否則我們接著判斷里面的兩個字符是不是相等，以此類推。基于這個思路，我們不難寫出如下代碼：
/* 判斷起始指針為pBegin，結(jié)束指針為pEnd的字符串是否對稱 */ 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)過比較，就能得到最長的對稱子字符串的長度了。于是，我們可以寫出如下代碼：
/* 取得所有對稱子串的最大長度 時間復雜度： O(n^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（n^3）。
??????? 通常O（n^3）不會是一個高效的算法。如果我們仔細分析上述方法的比較過程，我們就能發(fā)現(xiàn)其中有很多重復的比較。假設(shè)我們需要判斷一個子字符串具有aAa的形式（A是aAa的子字符串，可能含有多個字符）。我們先把pFirst指向最前面的字符a，把pLast指向最后面的字符a，由于兩個字符相同，我們在IsSymtical函數(shù)內(nèi)部向后移動pFirst，向前移動pLast，以判斷A是不是對稱的。接下來若干步驟之后，由于A也是輸入字符串的一個子字符串，我們需要再一次判斷它是不是對稱的。也就是說，我們重復多次地在判斷A是不是對稱的。
??????? 造成上述重復比較的根源在于IsSymmetrical的比較是從外向里進行的。在判斷aAa是不是對稱的時候，我們不知道A是不是對稱的，因此需要花費O（n）的時間來判斷。下次我們判斷A是不是對稱的時候，我們?nèi)匀恍枰狾（n）的時間。
??????? 如果我們換一種思路，我們從里向外來判斷。也就是我們先判斷子字符串A是不是對稱的。如果A不是對稱的，那么向該子字符串兩端各延長一個字符得到的字符串肯定不是對稱的。如果A對稱，那么我們只需要判斷A兩端延長的一個字符是不是相等的，如果相等，則延長后的字符串是對稱的。因此在知道A是否對稱之后，只需要O（1）的時間就能知道aAa是不是對稱的。
?????? 我們可以根據(jù)從里向外比較的思路寫出如下代碼：
/* 取得所有對稱子串的最大長度 時間復雜度： O(n^2) */int GetLongestSymmetricalLength(char* pString) {if(pString == NULL)return 0;int symmeticalLength = 1;char* pChar = pString;while(*pChar != '\0'){// Substrings with odd lengthchar* left = pChar - 1;char* right = pChar + 1;while(left >= pString && *right != '\0' && *left == *right){left--;right++;}int newLength = right - left - 1; //退出while循環(huán)時，*left != *rightif(newLength > symmeticalLength)symmeticalLength = newLength; // Substrings with even lengthleft = pChar;right = pChar + 1;while(left >= pString && *right != '\0' && *left == *right){left--;right++;}newLength = right - left - 1; //退出while循環(huán)時，*left != *rightif(newLength > symmeticalLength)symmeticalLength = newLength;pChar++;}return symmeticalLength; }??????? 由于子字符串的長度可能是奇數(shù)也可能是偶數(shù)。長度是奇數(shù)的字符串是從只有一個字符的中心向兩端延長出來，而長度為偶數(shù)的字符串是從一個有兩個字符的中心向兩端延長出來。因此我們的代碼要把這種情況都考慮進去。
?????? 在上述代碼中，我們從字符串的每個字符串兩端開始延長，如果當前的子字符串是對稱的，再判斷延長之后的字符串是不是對稱的。由于總共有O（n）個字符，每個字符可能延長O（n）次，每次延長時只需要O（1）就能判斷出是不是對稱的，因此整個函數(shù)的時間效率是O（n^2）。
?
回文串定義：“回文串”是一個正讀和反讀都一樣的字符串，比如“l(fā)evel”或者“noon”等等就是回文串。
回文子串，顧名思義，即字符串中滿足回文性質(zhì)的子串。
經(jīng)常有一些題目圍繞回文子串進行討論，比如 HDOJ_3068_最長回文，求最長回文子串的長度。樸素算法是依次以每一個字符為中心向兩側(cè)進行擴展，顯然這個復雜度是O(N^2)的，關(guān)于字符串的題目常用的算法有KMP、后綴數(shù)組、AC自動機，這道題目利用擴展KMP可以解答，其時間復雜度也很快O(N*logN)。但是，今天筆者介紹一個專門針對回文子串的算法，其時間復雜度為O(n)，這就是manacher算法。
大家都知道，求回文串時需要判斷其奇偶性，也就是求aba和abba的算法略有差距。然而，這個算法做了一個簡單的處理，很巧妙地把奇數(shù)長度回文串與偶數(shù)長度回文串統(tǒng)一考慮，也就是在每個相鄰的字符之間插入一個分隔符，串的首尾也要加，當然這個分隔符不能再原串中出現(xiàn)，一般可以用‘#’或者‘$’等字符。例如：
原串：abaab
新串：#a#b#a#a#b#
這樣一來，原來的奇數(shù)長度回文串還是奇數(shù)長度，偶數(shù)長度的也變成以‘#’為中心的奇數(shù)回文串了。
接下來就是算法的中心思想，用一個輔助數(shù)組P記錄以每個字符為中心的最長回文半徑，也就是P[i]記錄以Str[i]字符為中心的最長回文串半徑。P[i]最小為1，此時回文串為Str[i]本身。
我們可以對上述例子寫出其P數(shù)組，如下
新串： # a # b # a # a # b #
P[]? :? 1 2 1 4 1 2 5 2 1 2 1
我們可以證明P[i]-1就是以Str[i]為中心的回文串在原串當中的長度。
證明：
1、顯然L=2*P[i]-1即為新串中以Str[i]為中心最長回文串長度。
2、以Str[i]為中心的回文串一定是以#開頭和結(jié)尾的，例如“#b#b#”或“#b#a#b#”所以L減去最前或者最后的‘#’字符就是原串中長度的二倍，即原串長度為(L-1)/2，化簡的P[i]-1。得證。
依次從前往后求得P數(shù)組就可以了，這里用到了DP(動態(tài)規(guī)劃)的思想，也就是求P[i]的時候，前面的P[]值已經(jīng)得到了，我們利用回文串的特殊性質(zhì)可以進行一個大大的優(yōu)化。我先把核心代碼貼上：
if(MaxId>i) {p[i]=Min(p[2*id-i],MaxId-i); }那么這句話是怎么得來的呢，其實就是利用了回文串的對稱性，如下圖：
j=2*id-1即為i關(guān)于id的對稱點，根據(jù)對稱性，P[j]的回文串也是可以對稱到i這邊的,但是如果P[j]的回文串對稱過來以后超過MaxId的話，超出部分就不能對稱過來了，如下圖，所以這里P[i]為的下限為兩者中的較小者，p[i]=Min(p[2*id-i],MaxId-i)。
算法的有效比較次數(shù)為MaxId次，所以說這個算法的時間復雜度為O(n)。
附HDOJ_3068_最長回文代碼：
#include <stdio.h>#define M 110010char b[M],a[M<<1]; int p[M<<1];int Min(int a,int b) {return a<b?a:b; }int main(void) {int i,n,id,MaxL,MaxId;while(scanf("%s",&b[1])!=EOF){MaxL=MaxId=0;for(i=1;b[i]!='\0';i++){a[(i<<1)]=b[i];a[(i<<1)+1]='#';}a[0]='?';a[1]='#';n=(i<<1)+2;a[n]=0;MaxId=MaxL=0;for(i=1;i<n;i++){if(MaxId>i){p[i]=Min(p[2*id-i],MaxId-i);}else{p[i]=1;}while(a[i+p[i]]==a[i-p[i]]){p[i]++;}if(p[i]+i>MaxId){MaxId=p[i]+i;id=i;}if(p[i]>MaxL){MaxL=p[i];}}printf("%d\n",MaxL-1);}return 0; }
總結(jié)
以上是生活随笔為你收集整理的程序员面试100题之一：对称字符串的最大长度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 约瑟夫环的数学优化方法
- 下一篇： 程序员面试100题之三：不用＋、－、×、