程序員編程藝術(shù)第十二~十五章：中簽概率，IP訪問次數(shù)，回文等問題（初稿）
作者：上善若水.qinyu，BigPotato，luuillu，well，July。編程藝術(shù)室出品。
前言
本文的全部稿件是由我們編程藝術(shù)室的部分成員：上善若水.qinyu，BigPotato，luuillu，well，July共同完成，共分4個部分，即4道題：
- 第一部分、從一道題，漫談數(shù)據(jù)結(jié)構(gòu)、以及壓縮、位圖算法，由上善若水.qinyu完成，
- 第二部分、遍歷n個元素取出等概率隨機(jī)取出其中之一元素，由BigPotato完成，
- 第三部分、提取出某日訪問百度次數(shù)最多的那個IP，由luuillu完成，
- 第四部分、回文判斷，由well完成。全文由July統(tǒng)稿完成。
由于本人在這周時間上實在是過于倉促，來不及過多整理，所以我盡量保持上述我的幾位伙伴的原話原文，基本沒做多少改動。因此，標(biāo)明為初稿，以后會更加詳盡細(xì)致的進(jìn)行修補(bǔ)完善。
前十一章請見這：程序員編程藝術(shù)第一~十章集錦與總結(jié)。吾以咱們編程藝術(shù)室的朋友為傲，以能識盡天下各路朋友為傲，以諸君為傲。
第一部分、從一道題，漫談數(shù)據(jù)結(jié)構(gòu)、以及壓縮、位圖算法
海量數(shù)據(jù)處理往往會很有趣，有趣在什么地方呢？
- 空間，available的內(nèi)存不夠，需要反復(fù)交換內(nèi)存
- 時間，速度太慢不行，畢竟那是海量數(shù)據(jù)
- 處理，數(shù)據(jù)是一次調(diào)用還是反復(fù)調(diào)用，因為針對時間和空間，通常來說，多次調(diào)用的話，勢必會增加預(yù)處理以減少每次調(diào)用的時候的時間代價。
題目如下
7、騰訊面試題：給40億個不重復(fù)的unsignedint的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？
分析：1個unsigned int占用4字節(jié)，40億大約是4G個數(shù)不到，那么一共大約要用16G的內(nèi)存空間，如果內(nèi)存不夠大，反復(fù)和硬盤交換數(shù)據(jù)的話，后果不堪設(shè)想。
那么怎么儲存這么多的數(shù)據(jù)呢？還記得伴隨數(shù)組么？還是那種思想，利用內(nèi)存地址代替下標(biāo)。
先舉例，在內(nèi)存中應(yīng)該是1個byte=8bit，那么明顯有
0 = 0000 0000
255 = 1111 1111
69 = 0100 0101
那么69可以表示0.2.6三個數(shù)存在，其余的7以下的數(shù)不存在，0表示0-7都不存在，255表示0-7都存在，這就是位圖算法：通過全部置0，存在置1，這樣一種模式來通過連續(xù)的地址存貯數(shù)據(jù)，和檢驗數(shù)據(jù)的方法。
那么1個 unsigned int代表多少個數(shù)呢？1個unsigned int 是一個2^32以內(nèi)的數(shù)，那么也就是這樣的1個數(shù)，可以表示32個數(shù)是否存在。同理申請一個unsigned int的數(shù)組a[n]則可以表示連續(xù)的(n+1)*32的數(shù)。也就是a[0]表示0-31的數(shù)是否存在，a[1]表示32-63的數(shù)是否存在，依次類推。
這時候需要用多大的內(nèi)存呢？
16g/32=512M
512M和16G之間的區(qū)別，卻是是否一個32位尋址的CPU能否辦得到的事兒了，眾所周知，32位CPU最大尋址不超過4G，固然，你會說，現(xiàn)在都是64位的CPU之類的云云，但是，對于底層的設(shè)計者來說，尋址范圍越小越好操控的事實是不爭的。
問題到這里，其實基本上已經(jīng)完事了，判斷本身，在位圖算法這里就是找到對應(yīng)的內(nèi)存位置是否為1就可以了。
當(dāng)數(shù)據(jù)超出可接受范圍之后…
當(dāng)然，下面就要開始說一說，當(dāng)數(shù)據(jù)超出了可以接受的范圍之后的事情了。比如， 2^66范圍的數(shù)據(jù)檢索，也會是一個問題
4倍于64位CPU尋址范圍，如果加上CPU本身的偏移寄存器占用的資源，可能應(yīng)該是6-8個64位U的尋址范圍，如果反復(fù)從內(nèi)存到硬盤的讀寫，過程本身就是可怕的。
算法，更多的是用來解決瓶頸的，就想現(xiàn)在，根本不用考慮內(nèi)存超出8M的問題，但是20年前，8086的年代，內(nèi)存4M，或者內(nèi)存8M，你怎么處理?固然做軟件的不需要完全考慮摩爾定律，但是摩爾定律絕對是影響軟件和算法編寫者得想法的。
再比如，烏克蘭俄羅斯的一批壓縮高手，比如國內(nèi)有名的R大，為什么壓縮會出現(xiàn)？就是因為，要么存不下，要么傳輸時間過長。網(wǎng)絡(luò)再好，64G的高清怎么的也得下載個一段時間吧。海量數(shù)據(jù)處理，永遠(yuǎn)是考慮超過了當(dāng)前硬件條件的時候，該怎么辦？！
那么我們可以發(fā)現(xiàn)一個更加有趣的問題，如果存不下，但是還要存，怎么辦！
壓縮！這里簡單的說一嘴，無損壓縮常見的為Huffman算法和LZW(Lenpel-Ziv &Welch)壓縮算法，前者研究不多，后者卻經(jīng)常使用。
因為上面提到了位圖算法，我就用常見的位圖類的數(shù)據(jù)舉例：
以下引自我的摘抄出處忘記了，請作者見諒：
“對原始數(shù)據(jù)ABCCAABCDDAACCDB進(jìn)行LZW壓縮
原始數(shù)據(jù)中，只包括4個字符(Character),A,B,C,D,四個字符可以用一個2bit的數(shù)表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復(fù)字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原數(shù)據(jù)短了一些呢！
LZW算法的適用范圍
為了區(qū)別代表串的值(Code)和原來的單個的數(shù)據(jù)值(String)，需要使它們的數(shù)值域不重合，上面用0-3來代表A-D,那么AB就必須用大于3的數(shù)值來代替，再舉另外一個例子，原來的數(shù)值范圍可以用8bit來表示，那么就認(rèn)為原始的數(shù)的范圍是0～255，壓縮程序生成的標(biāo)號的范圍就不能為0～255（如果是0-255，就重復(fù)了）。只能從256開始，但是這樣一來就超過了8位的表示范圍了，所以必須要擴(kuò)展數(shù)據(jù)的位數(shù)，至少擴(kuò)展一位，但是這樣不是增加了1個字符占用的空間了么？但是卻可以用一個字符代表幾個字符，比如原來255是8bit,但是現(xiàn)在用256來表示254，255兩個數(shù)，還是劃得來的。從這個原理可以看出LZW算法的適用范圍是原始數(shù)據(jù)串最好是有大量的子串多次重復(fù)出現(xiàn)，重復(fù)的越多，壓縮效果越好。反之則越差，可能真的不減反增了。
偽代碼如下
1 STRING = get input character
2 WHILE there are still input characters DO
3 CHARACTER = get input character
4 IF STRING+CHARACTER is in the string table then
5 STRING = STRING+character
6 ELSE
7 output the code for STRING
8 add STRING+CHARACTER to the string table
9 STRING = CHARACTER
10 END of IF
11 END of WHILE
12 output the code for STRING
看過上面的適用范圍在聯(lián)想本題，數(shù)據(jù)有多少種，根據(jù)同余模的原理，可以驚人的發(fā)現(xiàn)，其實真的非常適合壓縮，但是壓縮之后，盡管存下了，在查找的時候，勢必又需要解碼，那么又回到了我們當(dāng)初學(xué)習(xí)算法時候，的那句經(jīng)典話，算法本身，就是為了解決時間和空間的均衡問題，要么時間換空間，要么空間換時間。
更多的，請讀者自行思考，因為，壓縮本身只是想引起讀者思考，已經(jīng)是題外話了~本部分完--上善若水.qinyu。
第二部分、遍歷n個元素取出等概率隨機(jī)取出其中之一元素
問題描述
1．一個文件中含有n個元素，只能遍歷一遍，要求等概率隨機(jī)取出其中之一。
先講一個例子，5個人抽5個簽，只有一個簽意味著“中簽”，輪流抽簽，那么這種情況，估計這5個人都不會有異議，都覺得這種方法是公平的，這確實也是公平的，“抓鬮”的方法已經(jīng)有很長的歷史了，要是不公平的話老祖先們就不干了。
或許有人覺得先抓的人中簽的概率會大一些，因為要是前面的人中了，后面的中簽概率就是0了，也可能有人會覺得后面抓的人更有優(yōu)勢，因為前面拿去了不中的簽，后面中簽的概率就大，那么我們就計算一下吧。
問題分析
第一個人中簽的概率是1/5,
第二個人中簽的情況只能在第一個人未中時才有可能，所以他中的概率是4/5 X 1/4 = 1/5（4/5表示第一個人未中，1/4表示在剩下的4個簽里中簽的概率），所以，第二個人最終的中簽概率也是1/5，
同理，第三個人中簽的概率為：第一個人未中的概率X 第二個人未中的概率X第三個人中的概率，即為：4/5 X 3/4 X 1/3 = 1/5，
一樣的可以求出第四和第五個人的概率都為1/5，也就是說先后順序不影響公平性。
說這個問題是要說明這種前后有關(guān)聯(lián)的事件的概率計算的方式，我們回到第1個問題。前幾天我的一個同學(xué)電面百度是被問到這個問題，他想了想回答說，依次遍歷，遇到每一個元素都生成一個隨機(jī)數(shù)作為標(biāo)記，如果當(dāng)前生成的隨機(jī)數(shù)大于為之前保留的元素生成的隨機(jī)數(shù)就替換，這樣操作直到文件結(jié)束。
但面試官問到：如果生成的隨機(jī)數(shù)和之前保留的元素的隨機(jī)數(shù)一樣大的話，要不要替換呢？
你也許會想，一個double的范圍可以是-1.79E+308 ~ +1.79E+308，要讓兩個隨機(jī)生成的double相等的概率不是一般的微乎其微啊！但計算機(jī)世界里有條很讓人傷心的“真理”：可能發(fā)生的事件，總會發(fā)生！
那我們遇到這種情況，是換還是不換？To be or not to be， that’s a question！
就好比，兩個人百米賽跑，測出來的時間一樣，如果只能有一個人得冠軍的話，對于另一個人始終是不公平的，那么只能再跑一次，一決雌雄了！
我的策略
下面，說一個個人認(rèn)為比較滿足要求的選取策略：
你要是給面試官說明了這樣一個策略后，面試官百分之一千會問你這樣做是等概率嗎？那我們來證明一下。
證明
在遍歷到第1個元素的時候，即L為1，那么r%L必然為0，所以e為第一個元素，p=100%，
遍歷到第2個元素時，L為2，r%L==0的概率為1/2, 這個時候，第1個元素不被替換的概率為1X(1-1/2)=1/2,
第1個元素被替換，也就是第2個元素被選中的概率為1/2 = 1/2,你可以看到，只有2時，這兩個元素是等概率的機(jī)會被選中的。
繼續(xù)，遍歷到第3個元素的時候，r%L==0的概率為1/3，前面被選中的元素不被替換的概率為1/2 X (1-1/3)=1/3,前面被選中的元素被替換的概率，即第3個元素被選中的概率為1/3
歸納法證明，這樣走到第L個元素時，這L個元素中任一被選中的概率都是1/L，那么走到L+1時，第L+1個元素選中的概率為1/(L+1), 之前選中的元素不被替換，即繼續(xù)被選中的概率為1/L X ( 1-1/(L+1) ) = 1/(L+1)。證畢。
也就是說，走到文件最后，每一個元素最終被選出的概率為1/n， n為文件中元素的總數(shù)。好歹我們是一個技術(shù)博客，看不到一丁點(diǎn)代碼多少有點(diǎn)遺憾，給出一個選取策略的偽代碼，如下：
偽代碼
Element RandomPick(file):
Int length = 1;
While( length <= file.size )
If( rand() % length == 0)
Picked = File[length];
Length++;
Return picked
近日，看見我的一些同學(xué)在他們的面經(jīng)里面常推薦結(jié)構(gòu)之法算法之道這個博客，感謝東南大學(xué)計算機(jī)學(xué)院即將找工作的同學(xué)們對本博的關(guān)注，歡迎批評指正！--BigPotato。
第三部分、提取出某日訪問百度次數(shù)最多的那個IP
問題描述：海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。
方法: 計數(shù)法
假設(shè)一天之內(nèi)某個IP訪問百度的次數(shù)不超過40億次,則訪問次數(shù)可以用unsigned表示.用數(shù)組統(tǒng)計出每個IP地址出現(xiàn)的次數(shù), 即可得到訪問次數(shù)最大的IP地址.
IP地址是32位的二進(jìn)制數(shù),所以共有N=2^32=4G個不同的IP地址, 創(chuàng)建一個unsigned count[N];的數(shù)組,即可統(tǒng)計出每個IP的訪問次數(shù),而sizeof(count) == 4G*4=16G, 遠(yuǎn)遠(yuǎn)超過了32位計算機(jī)所支持的內(nèi)存大小,因此不能直接創(chuàng)建這個數(shù)組.下面采用劃分法解決這個問題.
假設(shè)允許使用的內(nèi)存是512M, 512M/4=128M 即512M內(nèi)存可以統(tǒng)計128M個不同的IP地址的訪問次數(shù).而N/128M =4G/128M = 32 ,所以只要把IP地址劃分成32個不同的區(qū)間,分別統(tǒng)計出每個區(qū)間中訪問次數(shù)最大的IP, 然后就可以計算出所有IP地址中訪問次數(shù)最大的IP了.
因為2^5=32, 所以可以把IP地址的最高5位作為區(qū)間編號, 剩下的27為作為區(qū)間內(nèi)的值,建立32個臨時文件,代表32個區(qū)間,把相同區(qū)間的IP地址保存到同一的臨時文件中.
例如:
ip1=0x1f4e2342
ip1的高5位是id1 = ip1 >>27 = 0x11 = 3
ip1的其余27位是value1 = ip1 &0x07ffffff = 0x074e2342
所以把 value1 保存在tmp3文件中.
由id1和value1可以還原成ip1, 即 ip1 =(id1<<27)|value1
按照上面的方法可以得到32個臨時文件,每個臨時文件中的IP地址的取值范圍屬于[0-128M),因此可以統(tǒng)計出每個IP地址的訪問次數(shù).從而找到訪問次數(shù)最大的IP地址
程序源碼:
test.cpp是c++源碼.
- #include <fstream>
- #include <iostream>
- #include <ctime>
-
- using namespace std;
- #define N 32 //臨時文件數(shù)
-
- #define ID(x) (x>>27) //x對應(yīng)的文件編號
- #define VALUE(x) (x&0x07ffffff) //x在文件中保存的值
- #define MAKE_IP(x,y) ((x<<27)|y) //由文件編號和值得到IP地址.
-
- #define MEM_SIZE 128*1024*1024 //需分配內(nèi)存的大小為 MEM_SIZE*sizeof(unsigned)
-
- char* data_path="D:/test/ip.dat"; //ip數(shù)據(jù)
-
- //產(chǎn)生n個隨機(jī)IP地址
- void make_data(const int& n)
- {
- ofstream out(data_path,ios::out|ios::binary);
- srand((unsigned)(time(NULL)));
- if (out)
- {
- for (int i=0; i<n; ++i)
- {
- unsigned val=unsigned(rand());
- val = (val<<24)|val; //產(chǎn)生unsigned類型的隨機(jī)數(shù)
-
- out.write((char *)&val,sizeof (unsigned));
- }
- }
- }
-
- //找到訪問次數(shù)最大的ip地址
- int main()
- {
- //make_data(100); //
- make_data(100000000); //產(chǎn)生測試用的IP數(shù)據(jù)
- fstream arr[N];
-
- for (int i=0; i<N; ++i) //創(chuàng)建N個臨時文件
- {
- char tmp_path[128]; //臨時文件路徑
- sprintf(tmp_path,"D:/test/tmp%d.dat",i);
- arr[i].open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary); //打開第i個文件
-
- if( !arr[i])
- {
- cout<<"open file"<<i<<"error"<<endl;
- }
- }
-
- ifstream infile(data_path,ios::in|ios::binary); //讀入測試用的IP數(shù)據(jù)
- unsigned data;
-
- while(infile.read((char*)(&data), sizeof(data)))
- {
- unsigned val=VALUE(data);
- int key=ID(data);
- arr[ID(data)].write((char*)(&val), sizeof(val)); //保存到臨時文件件中
- }
-
- for(unsigned i=0; i<N; ++i)
- {
- arr[i].seekg(0);
- }
- unsigned max_ip = 0; //出現(xiàn)次數(shù)最多的ip地址
- unsigned max_times = 0; //最大只出現(xiàn)的次數(shù)
-
- //分配512M內(nèi)存,用于統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)
- unsigned *count = new unsigned[MEM_SIZE];
-
- for (unsigned i=0; i<N; ++i)
- {
- memset(count, 0, sizeof(unsigned)*MEM_SIZE);
-
- //統(tǒng)計每個臨時文件件中不同數(shù)字出現(xiàn)的次數(shù)
- unsigned data;
- while(arr[i].read((char*)(&data), sizeof(unsigned)))
- {
- ++count[data];
- }
-
- //找出出現(xiàn)次數(shù)最多的IP地址
- for(unsigned j=0; j<MEM_SIZE; ++j)
- {
- if(max_times<count[j])
- {
- max_times = count[j];
- max_ip = MAKE_IP(i,j); // 恢復(fù)成原ip地址.
- }
- }
- }
- delete[] count;
- unsigned char *result=(unsigned char *)(&max_ip);
- printf("出現(xiàn)次數(shù)最多的IP為:%d.%d.%d.%d,共出現(xiàn)%d次",
- result[0], result[1], result[2], result[3], max_times);
- }
執(zhí)行結(jié)果.
--luuillu。
第四部分、回文判斷
（初稿，寫的比較急，請審閱、增補(bǔ)、修改）
回文判斷是一類典型的問題，尤其是與字符串結(jié)合后呈現(xiàn)出多姿多彩，在實際中使用也比較廣泛，而且也是面試題中的常客，所以本文就結(jié)合幾個典型的例子來體味下回文之趣。
回文，英文palindrome，指一個順著讀和反過來讀都一樣的字符串，比如 madam、我愛我，這樣的短句在智力性、趣味性和藝術(shù)性上都頗有特色，中國歷史上還有很多有趣的回文詩呢 ：）
一、回文判斷
那么，我們的第一個問題就是：判斷一個字串是否是回文
通過對回文字串的考察，最直接的方法顯然是將字符串逆轉(zhuǎn)，存入另外一個字符串，然后比較原字符串和逆轉(zhuǎn)后的字符串是否一樣，一樣就是回文，這個方法的時空復(fù)雜度都是 O(n)。
我們還很容易想到只要從兩頭開始同時向中間掃描字串，如果直到相遇兩端的字符都一樣，那么這個字串就是一個回文。我們只需要維護(hù)頭部和尾部兩個掃描指針即可，代碼如下：
- /**
- *check weather s is a palindrome, n is the length of string s
- *Copyright(C) fairywell 2011
- */
- bool IsPalindrome(const char *s, int n)
- {
- if (s == 0 || n < 1) return false; // invalid string
- char *front, *back;
- front = s; back = s + n - 1; // set front and back to the begin and endof the string
- while (front < back) {
- if (*front != *back) return false; // not a palindrome
- ++front; --back;
- }
- return true; // check over, it's a palindrome
-
- }
這是一個直白且效率不錯的實現(xiàn)，只需要附加 2 個額外的指針，在 O(n) 時間內(nèi)我們可以判斷出字符串是否是回文。
是否還有其他方法？呵呵，聰明的讀者因該想到了不少變種吧，不過時空復(fù)雜度因為不會有顯著提升了（為什么？），下面再介紹一種回文判斷方法，先上代碼：
- /**
- *check weather s is a palindrome, n is the length of string s
- *Copyright(C) fairywell 2011
- */
- bool IsPalindrome2(const char *s, int n)
- {
- if (s == 0 || n < 1) return false; // invalid string
- char *first, *second;
- int m = ((n>>1) - 1) >= 0 ? (n>>1) - 1 : 0; // m is themiddle point of s
- first = s + m; second = s + n - 1 - m;
- while (first >= s)
- if (s[first--] !=s[second++]) return false; // not equal, so it's not apalindrome
- return true; // check over, it's a palindrome
- }
代碼略有些小技巧，不過相信我們聰明的讀者已經(jīng)看清了意思，這里就是從中間開始、向兩邊擴(kuò)展查看字符是否相等的一種方法，時空復(fù)雜度和上一個方法是一模一樣的，既然一樣，那么我們?yōu)槭裁催€需要這種方法呢？首先，世界的美存在于它的多樣性；其次，我們很快會看到，在某些回文問題里面，這個方法有著自己的獨(dú)到之處，可以方便的解決一類問題。
那么除了直接用數(shù)組，我們還可以采用其他的數(shù)據(jù)結(jié)構(gòu)來判斷回文嗎呢？請讀者朋友稍作休息想想看。相信我們聰明的讀者肯定想到了不少好方法吧，也一定想到了經(jīng)典的單鏈表和棧這兩種方法吧，這也是面試中常常出現(xiàn)的兩種回文數(shù)據(jù)結(jié)構(gòu)類型。
對于單鏈表結(jié)構(gòu)，處理的思想不難想到：用兩個指針從兩端或者中間遍歷并判斷對應(yīng)字符是否相等。所以這里的關(guān)鍵就是如何朝兩個方向遍歷。單鏈表是單向的，所以要向兩個方向遍歷不太容易。一個簡單的方法是，用經(jīng)典的快慢指針的方法，定位到鏈表的中間位置，將鏈表的后半逆置，然后用兩個指針同時從鏈表頭部和中間開始同時遍歷并比較即可。
對于棧就簡單些，只需要將字符串全部壓入棧，然后依次將各字符出棧，這樣得到的就是原字符串的逆置串，分別和原字符串各個字符比較，就可以判斷了。
二、回文的應(yīng)用
我們已經(jīng)了解了回文的判斷方法，接下來可以來嘗試回文的其他應(yīng)用了。回文不是很簡單的東西嗎，還有其他應(yīng)用？是的，比如：查找一個字符串中的最長回文字串
Hum，還是請讀者朋友們先自己想想看看。嗯，有什么好方法了嗎？枚舉所有的子串，分別判斷其是否為回文？這個思路是正確的，但卻做了很多無用功，如果一個長的子串包含另一個短一些的子串，那么對子串的回文判斷其實是不需要的。
那么如何高效的進(jìn)行判斷呢？既然對短的子串的判斷和包含它的長的子串的判斷重復(fù)了，我們何不復(fù)用下短的子串的判斷呢（哈，算法里也跑出軟件工程了），讓短的子串的判斷成為長的子串的判斷的一個部分！想到怎么做了嗎？Aha，沒錯，擴(kuò)展法。從一個字符開始，向兩邊擴(kuò)展，看看最多能到多長，使其保持為回文。這也就是為什么我們在上一節(jié)里面要提出 IsPalindrome2 的原因。
具體而言，我們可以枚舉中心位置，然后再在該位置上用擴(kuò)展法，記錄并更新得到的最長的回文長度，即為所求。代碼如下：
- /**
- *find the longest palindrome in a string, n is the length of string s
- *Copyright(C) fairywell 2011
- */
- int LongestPalindrome(const char *s, int n)
- {
- int i, j, max;
- if (s == 0 || n < 1) return 0;
- max = 0;
- for (i = 0; i < n; ++i) { // i is the middle point of the palindrome
- for (j = 0; (i-j >= 0) && (i+j < n); ++j) // if the lengthof the palindrome is odd
- if (s[i-j] != s[i+j]) break;
- if (j*2+1 > max) max = j * 2 + 1;
- for (j = 0; (i-j >= 0) && (i+j+1 < n); ++j) // for theeven case
- if (s[i-j] != s[i+j+1]) break;
- if (j*2+2 > max) max = j * 2 + 2;
- }
- return max;
- }
代碼稍微難懂一點(diǎn)的地方就是內(nèi)層的兩個 for 循環(huán)，它們分別對于以 i 為中心的，長度為奇數(shù)和偶數(shù)的兩種情況，整個代碼遍歷中心位置 i 并以之?dāng)U展，找出最長的回文。
當(dāng)然，還有更先進(jìn)但也更復(fù)雜的方法，比如用 s 和逆置 s' 的組合 s$s' 來建立后綴樹的方法也能找到最長回文，但構(gòu)建的過程比較復(fù)雜，所以在實踐中用的比較少，感興趣的朋友可以參考相應(yīng)資料。
回文的內(nèi)容還有不少，但主要的部分通過上面的內(nèi)容相信大家已經(jīng)掌握，希望大家能抓住實質(zhì)，在實踐中靈活運(yùn)用，回文的內(nèi)容我就暫時介紹到這里了，謝謝大家--well。
附注：
- 如果讀者對本文的內(nèi)容或形式，語言和表達(dá)不甚滿意。完全理解。我之前也跟編程藝術(shù)室內(nèi)的朋友們開玩笑的說：我暫不做任何修改，題目會標(biāo)明為初稿。這樣的話，你們才會相信或者知曉，你們的才情只有通過我的語言和表達(dá)才能最大限度的發(fā)揮出來，被最廣泛的人輕而易舉的所認(rèn)同和接受（不過，以上4位兄弟的思維靈活度都在本人之上）。呵呵，開個玩笑。
- 本文日后會抽取時間再做修補(bǔ)和完善。若有任何問題，歡迎隨時不吝指正。謝謝。
完。