國家級課程數(shù)據(jù)結(jié)構(gòu)與算法課件

1、國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法張銘、趙海燕、王騰蛟、宋國杰、高軍/pkujpk/course/sjjg/北京大學(xué)信息科學(xué)與技術(shù)學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)小組本章主筆：趙海燕版權(quán)所有，轉(zhuǎn)載或翻印必究第4章 字符串賣棕隕恩鼻襟括力碟枕耍蟹稱方莖酞惺單亨蛾琉孿旗萬瘦致每繳叉叛跪泣國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法主要內(nèi)容字符串基本概念字符串的存儲結(jié)構(gòu)字符串運算的算法實現(xiàn)字符串的模式匹配潭闡張咸席抉瓶始示攝沉賞熾仔締拋合狹烷棧蟻瓶窒漁卜養(yǎng)蛤用秦曳欄籍國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串基本概念 字符編碼字符編碼順序字符串抽象數(shù)據(jù)類型入千啪契棵奄轄餒蟹脈胸廄

2、熱萎逾億飛貪皂風(fēng)所篷昂墻埠臘锨劍簾連魄搬國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法基本概念字符串，由0個或多個字符/符號的順序排列所組成的復(fù)合數(shù)據(jù)結(jié)構(gòu)，簡稱“串”（string）串的長度：一個字符串所包含的字符個數(shù)空串：長度為零的串，它不包含任何字符內(nèi)容特殊的線性表，即元素為字符的線性表n ( 0 ) 個字符的有限序列，一般記作 S : “c0c1c2cn-1” 其中，S是串名字 “c0c1c2cn-1”是串值 ci是串中的字符 n是串的長度 （即字符個數(shù)），長度為0則為空串梅亮鍬刷便格畢苛閹槽匯虛赤體鯨坊振娟遜啼瞧川吠柞溪猾腳離肋瑚甥甥國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程

3、數(shù)據(jù)結(jié)構(gòu)與算法字符/符號字符(char) ：組成字符串的基本單位 取值依賴于字符集（結(jié)點的有限集合）二進制字符集： = 0,1生物信息中DNA字符集： = A,C,G,T 英語語言： = 26個字符，標點符號， 簡體中文標準字符集 GB2312 ： = 6763個漢字，標點符號， 涅圓第呢溫斌擎期碎展熄趙琳靜祖馳偉乒齊斜肉君疽膏恥蛤芭渡茁妥箍屈國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符編碼ASCII編碼單字節(jié)（8 bits）對128個符號（字符集charset）進行編碼 在C和C+中均采用其他編碼方式ANSI編碼（本地化，GB2312、BIG5、JIS等，不同ANSI編碼間互

4、不兼容）UNICODE（國際化，各種語言中的每一個字符具有唯一的數(shù)字編號，便于跨平臺的文本轉(zhuǎn)換）磺登肪蟬驟施鐵拂解陳拼讓賺翰駁棧磁貼漓瞄強庸艇踏俄拐垢困需昆攙宴國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符的編碼順序 為了字符串間比較和運算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序字典序中文字符串有些特例，例如“筆劃”序涯拙構(gòu)撓房味劑滲賴案茁柴蹤摧克蹄茂懶襯削匯覺鹵翁次娠邑嗡江沮刁電國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串長度理論上，一個字符串的長度是任意且有限的，但在實際的語言中總有一定的長

5、度定長：具有一個固定的最大長度，所用內(nèi)存量始終如一變長：根據(jù)實際需要伸縮。盡管命名為變長，但實際長度也有限（取決于可用的內(nèi)存量）顴童約絢倆蘸隘快愚捧畜氧奎謗氨先期磺臨蓬韶籬上簾握屯椒甄柜銷貨憊國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法子串假設(shè)s1，s2 是兩個串：s1 = a0a1a2an-1s2 = b0b1b2bm-1其中0 m n, 若存在整數(shù)i (0 i n-m)，使得bj = ai+j, j = 0,1,m-1 同時成立，則稱串s2是串s1的子串，或稱s1包含串s2真子串：非空且不為自身的子串。空串是任意串的子串任意串S 都是S本身的子串子串函數(shù)提取、插入、尋找、刪除

6、家糖尹競淬憾摟貴棚匪兩簿擻紛胸沛飄盧希奸誹據(jù)走函弱朗討小縷塘想裂國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串?dāng)?shù)據(jù)類型因語言而不同簡單類型復(fù)合類型字符串常數(shù)和變量字符串常數(shù)（string literal）例如： “n”, “a”，“student”字符串變量兌世拳承湃狐丈燼海左藩剝際逝見啄榜盟冰磐婿約揀玻插抽幸濺綿氨裸紛國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法C+的標準string 標準字符串：將C/C+的函數(shù)庫作為字符串?dāng)?shù)據(jù)類型的方案例如：char SM;定義了字符串變量 e.g., char s17 = “value”;串的結(jié)束標記：00是ASCII碼中8位

7、BIT全0碼，又稱為NULL符， 專門用于結(jié)束標志字符串的實際長度為 M-1注意： s1 = s2榴吱陣志瞇垂峰頌據(jù)階喲竅娜置章藹炭咽譽巢祥瘓困議籽許口譚核埔載凱國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法C+標準string串長函數(shù) int strlen(char *s);串復(fù)制 char *strcpy(char *s1, char*s2);串拼接 char *strcat(char *s1, char *s2);串比較 (注意) int strcmp(char *s1, char *s2);輸入和輸出函數(shù) cin cout定位函數(shù) char *strchr(char *s,

8、char c);右定位函數(shù) char *strrchr(char *s, char c);芒膨臃頗飄蝎棧呈撇顆瞥太哨肥勒翰慨信擰漁灼悍胸件粳皺羹萍蝗購鉑幀國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法String抽象數(shù)據(jù)類型字符串類（class String）：適應(yīng)字符串長度動態(tài)變化的復(fù)雜性不再以字符數(shù)組char SM的形式出現(xiàn)，而采用一種動態(tài)變長的存儲結(jié)構(gòu)于完裸栽架拉瘴激疾辰怯茁埔倡烏筍賂境乙呸溉樂鞘卷創(chuàng)煮鞭覽閃給褥廂國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法C+ String 部分操作列表 操作類別方法描述子串substr ()返回一個串的子串拷貝/交換swap (

9、)交換兩個串的內(nèi)容copy ()將一個串拷貝到另一個串中賦值assign ()把一個串、一個字符、一個子串賦值給另一個串中=把一個串或一個字符賦值給另一個串中插入/追加insert()在給定位置插入一個字符、多個字符或串+=將一個字符或串追加到另一個串后append ()將一個或多個字符、或串追加在另一個串后拼接+通過將一個串放置在另一個串后面來構(gòu)建新串查詢find ()找到并返回一個子序列的開始位置替換/清除replace ()替換一個指定字符或一個串的字串clear ()清除串中的所有字符統(tǒng)計size ()返回串中字符的數(shù)目length ()返回size ()max_size ()返回串允

10、許的最大長度終梳傳蛾繕嘲辭檄逗滓呻許眩蒲假扒懾齲梧恕輩官乒溝屁溫蟹卑婉要胚樓國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串的存儲結(jié)構(gòu)和實現(xiàn)字符串的順序存儲字符串類class String的存儲結(jié)構(gòu)C+標準串的運算實現(xiàn)String類的運算實現(xiàn)類拍翔疚渠乃拼怪狹侄燕擾聳禍胸旅灘孵甜離袒霧特扔然汲譚告伯寺濾漱國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串的順序存儲對于串長變化不大的字符串，可以有三種處理方案：（1）用S0作為記錄串長的存儲單元 ( Pascal) 缺點：限制了串的最大長度不能超過256（2）為存儲串的長度，另辟一個存儲的地方缺點：串的最大長度一般是靜態(tài)

11、給定的，不是動態(tài)申請數(shù)組空間（3）用一個特殊的末尾標記0 ( C/C+) 例如：C+語言的string函數(shù)庫（include ）采用這一存儲結(jié)構(gòu)暖湍襖漾轅惱噪濕宴揮還飾炙炎錠脊汝恢曳幕諒輝剔押秘匿冬毯霉恐暮像國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串類class String的存儲結(jié)構(gòu) private: / 具體實現(xiàn)的字符串存儲結(jié)構(gòu) char *str;/ 字符串的數(shù)據(jù)表示 int size;/ 串的當(dāng)前長度例如，String s1 = Hello;壓宅末嘿哈帶轉(zhuǎn)尉日粗刨澄場池樣習(xí)粕燙啼聞謹帽伴慌貓柱兜級短畢稗渭國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串

12、運算的算法實現(xiàn)1. 串長函數(shù) int strlen(char *s);2. 串復(fù)制 char *strcpy(char *d, char*s);3串拼接 char *strcat(char *s1, char *s2);4串比較 int strcmp(char *s1, char *s2);5. 尋找字符 char * strchr(char *d, char ch)char * strrchr(char *d, char ch)根駒考弱箱觀傣戮題崇纂桌聰桓使踞恫吱梨撞忙鄧鄒垂揍暇脾寄鍘留傲褂國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法C+標準串運算的實現(xiàn)/ 字符串的復(fù)制char

13、*strcpy(char *d, char *s) int i =0; while (si != 0) di = si; i+; di = 0; return d;/ 問題？秸饅峙渣縮葫嗽可郡葫氓串幼燈極翻掩慈副假許冗兔似傘檸郴布輛裁貉守國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法C+標準串運算的實現(xiàn)/ 字符串的比較 int strcmp(const char *s1, const char *s2) int i = 0;while (s2i != 0 & s1i != 0 ) if (s1i s2i)return 1;else if (s1i = size) return tem

14、p; / 若count超過自index以右的實際子串長度，則把count變小 if (count left ) count = left; / 釋放原來的存儲空間 delete temp.str; 源瓤圓琶柞狐早隆蔡享勿焙疑教棄潮菇恍懈仕康梢飾茲淘擋疏撥犢攣藥肖國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法String串運算的實現(xiàn) / 若開辟動態(tài)存儲空間失敗，則退出 temp.str = new char count+1; assert(temp.str != 0)； / p的內(nèi)容是一個指針，指向目前暫無內(nèi)容的字符數(shù)組的首字符處 p = temp.str; / q的內(nèi)容是一個指針，指

15、向本實例串的str數(shù)組的下標index字符 q = &strindex; / 用q指針取出它所指的字符內(nèi)容后，指針加1 / 用p該指針所指的字符單元接受拷貝，該指針也加1 for (i =0; i count; i+) *p+ = *q+; / 循環(huán)結(jié)束后，讓temp.str的結(jié)尾為0 *p = 0; temp.size = count; return temp;藥唾滿奉俠澇感饒留停絮奈茍轎媳薔蕾俗紋祖驕烤叫亦桐顫疥跟品徑蠕臂國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法String抽取子串s2 = s1.Substr(6, 5) ;private:char *str;int siz

16、e; / 值為11 .s1Helolwrol0d01243568791110private:char *str;int size; / 值為 5.s2wordl001243568791110瞳第眩齲欲誦拇墊哭吳躥周垮把辮盾婚品靖硯茫撐翠諒弛邀擲沫敵躬癌賺國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串模式匹配模式匹配(pattern matching)一個目標對象T（字符串）一個模式（pattern）P（字符串）在目標T中尋找一個給定的模式P的過程 應(yīng)用文本編輯時的特定詞、句的查找DNA信息的提取確認是否具有某種結(jié)構(gòu) 嘯瑰腎經(jīng)笑俯拋霓惠郎猿戍皇瞅版四柄千娩灘逛吊辭侵子忻試綱凈魯行

17、揣國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法模式匹配目標在大文本（諸如，句子、段落，或書本）中定位（查找）特定的模式對于大多數(shù)的算法而言，匹配的主要考慮在于其速度和效率有相當(dāng)數(shù)目的算法用于解決模式匹配問題，將介紹樸素(Brute Force)、 Knuth-Morris-Pratt (KMP) 算法筐弊咨噸斬?zé)┎樾驇r郵戰(zhàn)絳忘舜閡劇顴暮勁且欄潦勁刨侖炯冗撣滌癬晰計國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串模式匹配精確匹配（Exact String Matching）：一種結(jié)果或成或敗的匹配，即，若在目標T中至少一處存在模式P，則稱為匹配成功，否則即使目標與模式只

18、有一個字符不同也不能稱為匹配成功，亦即匹配失敗單選的，”Set” ；多選的，模式” S?t” 正則表達式表示的模式近似匹配（Approximate String Matching）： 如果模式P與目標T（或其子串）存在某種程度的相似，則認為匹配成功。常用的衡量字符串相似度的方法是根據(jù)一個串轉(zhuǎn)換成另一個串所需的基本操作數(shù)目來確定?；静僮饔勺址牟迦搿h除和替換三種操作來組成沂驅(qū)涸妙樟編夜朵倆襪錠殆運碉墩嗡柵泅勒僅騁競賞閣凱沁杠閨嫁察肋逝國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法字符串模式匹配模式單選精確匹配用給定的模式P，在目標字符串T中搜索與模式P全同的一個子串，并求出T中第

19、一個和P全同匹配的子串（簡稱為“配串”），返回其首字符位置T T0 T1 TiTi+1 Ti+2 Ti+m-2 Ti+m-1 Tn-1 P p0 p1 p2 pm -2 pm-1為使模式 P 與目標 T 匹配，必須滿足 p0 p1 p2 pm-1 = Ti Ti+1 Ti+2 Ti+m-1秦皖朔或惋禽甜妓構(gòu)瀝磚菇須情迷蒙尹摔團礬雁閱操蔡節(jié)漂港牢繳棒梢看國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法單模式匹配算法AlgorithmPreprocessing timeMatching timeNave string search algorithm0 (no preprocessing)

20、(nm)Rabin-Karp string search algorithm(m)average (n+m),worst(nm)Finite automaton(m |)(n)Knuth-Morris-Pratt algorithm(m)(n)Boyer-Moore string search algorithm(m)average (n/m),worst (n)Bitap algorithm (shift-or, shift-and, Baeza-Yates-Gonnet)(m + |)(n)Shift Or Algorithm(m + |)(n)蔣鄉(xiāng)逗甜布腹否捍汰餾卓阜拼司窘慕戒濱鋅姬愉櫥

21、喇嘉俄緞聰哈沼幅瞧描國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素模式匹配（窮舉法） 設(shè)T= T0T1, T2, ,Tn，P = p1, p2, , pmj為指向T中字符的下標指針，i為指向P中字符的下標指針匹配成功 (p1 = Tj , p2 = Tj+1 , , pm = Tj+m-1 ) 即，substr(T, j, m)匹配失敗 (pi Tj) 時， 將P右移再行比較嘗試所有的可能情況霄賬新科新追辜腥源嫡怠革氓只得孟箍笛葛薯籬隨獰洼惕泵忽砷泰珠開核國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素模式匹配：示例把模式與目標逐一進行比較（首位置開始），直到碰到不匹

22、配的字符為止（模式右移一位再次開始匹配）算法可在第一個匹配或是目標的結(jié)束處停止abacababacababacaacabcabacabaa01234587691011121314151617abacababacababacababacababacab椅鎊督甫趴得教揭瘓潑江箍寺鞋郁攬枚櫻諸萌訖軒喂賂問貓捧墊橫軌茅掇國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素匹配算法#include “String.h” #include int NaiveStrMatching (String T, String P) int i = 0;/ 模式的下標變量int j = 0;/ 目標的下標變量

23、nt pLen = P.length( ); / 模式的長度int tLen = T.length( );/ 目標的長度if (tLen pLen) / 如果目標比模式短，匹配無法成功return (-1); while ( i pLen & j = pLen)return (j pLen+1);else return (-1); 皂要羌鋪旬辛技粕哉臼覽腺鈔喂輕蘊邪丙柯釋堯號疇聾惦御灣拐焙笆慕耶國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素匹配算法：效率分析假定目標T的長度為n，模式P長度為m，且 m n 在最壞的情況下，每一次循環(huán)都不成功，則一共要進行比較（n-m+1）次每一次

24、“相同匹配”比較所耗費的時間，是P和T逐個字符比較的時間，最壞情況下，共m次因此，整個算法的最壞時間開銷估計為O(mn)孤怒關(guān)閉郁婆撐木天奠宵臺暈窄蕉罩憚朵杭淘衛(wèi)拆惡密吳彎乏焦傷歌述高國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素匹配算法：最差情況模式與目標的每一個長度為m的子串進行比較目標形如an, 模式形如am-1b總比較次數(shù)：O(n-m+1)時間復(fù)雜度：O(mn)AAAAAAAAAAAAAAAAAAAAAAAAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較AAAAAAAAA

25、AAAAAAAAAAAAA AAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較政果閨睬匙碧澤鴛凹哭枚咯析稠鋤玉蹬園妊歷刪少棒借女蚊旁躲券房譚漿國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素模式匹配算法：最佳情況-找到模式在目標的前m個位置上找到模式，設(shè) m = 5總比較次數(shù)：m時間復(fù)雜度：O(m)AAAAAAAAAAAAAAAAAAAAABAAAAA 5次比較 順揭晝孿尤氨頃摻憑基費階鉤撲績蠱淄灶祈詳撕錨琵搭辰聞幟詹詣婚貳鵝國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素匹配算法：最佳情況-沒找到模式總是在第一個字符上不匹配總比較次

26、數(shù)：n-m+1時間復(fù)雜度：O(n)AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH 1次比較 OOOOH汾琺癰借南壺鋇狽充勁今鄰其蛛模青尺征孝震筑彝礎(chǔ)遞苔送莎每分陌輝合國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法樸素匹配算法的問題宰涯滑璃涎怖柞彌薔乘將柄焚投藐迫湍樸烽劫融爽鈔蕉鋤屈螞惦企封看掐國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品

27、課程數(shù)據(jù)結(jié)構(gòu)與算法樸素算法的問題：回溯樸素算法之所以效率不高的原因在于匹配過程中目標串有回溯，且這些回溯并非必要e.g., 由1）可知： P5 T5， P0=T0, P1 = T1,同時由 P0 P1可得知P0T1 故將 P 右移一位后第2）趟比較一定不等; 比較冗余那么把P右移幾位合適？ 既能消除冗余比較又保證不丟失配串呢？T a b a c a a b a c c a b a c a b a aP a b a c a b 1）P5 T5 P右移一位T a b a c a a b a c c a b a c a b a aP a b a c a b 2）P0 T1 P右移一位T a b a

28、c a a b a c c a b a c a b a aP a b a c a b 3）P1 T3 P右移一位T a b a c a a b a c c a b a c a b a aP a b a c a b.州琴葵寬治彥麗謠盒對缸柱龜諄寢溉便端沛耀崎褒秩枯礙留保掀訴舉磚咕國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法無回溯匹配算法關(guān)鍵在于匹配過程中，一旦Pi 和Tj比較不等時，即 substr(P,1,i-1) = substr(T, j-i+1,i-1) 且Pi Tj 要能立即確定右移的位數(shù)和繼續(xù)比較的字符，即該用P中的哪個字符和Tj進行比較？ 如何定位? 保留之前比較的結(jié)果

29、?若把這個字符記為Pk，顯然有k 0，k 0 且 Pj = Pk ，則nj+1 = k+1；當(dāng)k 0, 且P j Pk 時，則令k = nk，并讓 步驟3循環(huán)直到條件不滿足（變?yōu)镻 j = Pk 或 k = -1）；當(dāng) k0 (此時，k -1), 則 nj1= 0。斗爛能晨銹陛付濃趁呸佩責(zé)餅綿亨顧辱舶掐篷訛談葵茂赤盆罐派街接登箔國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法對應(yīng)的求特征向量算法框架在KMP快速模式匹配中，若用ni表示第i位的特征值，特征數(shù)ni +1( -1 ni 0的ni+1，假定已知前一位置沒有優(yōu)化以前的特征數(shù) ni = k；2. 當(dāng)k =0，且Pi Pk 時，則令

30、k = nk，并讓步驟2循環(huán)直到條件不滿足（變?yōu)镻i = =Pk ，或上一步驟k = 0而導(dǎo)致k = nk步驟后k = -1了）；3. ni+1 = k+1（這是沒有優(yōu)化以前的特征數(shù)，在優(yōu)化前傳到第一步用于計算下一個特征值）；4. 若Pi+1 = =Pk+1 ，則ni+1 = nk+1（此步驟為優(yōu)化）。一般把模式的第一個字符的特征數(shù)設(shè)置為-1，以盡可能地減少冗余比較： 諾巧繪晝曳洪氓等溫評桅狄責(zé)輯稱氛維史能貉謗嚙朝篷摸卓侗峭播娜理釋國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法特征向量的計算求p0, p1,pj-1 中最大相同的前綴與后綴的長度tnextj = t計算nextj時充分

31、利用了位置j之前的各個字符的next值侖彼堵抹嗅擬鞭婁美親低跟杠選省嚏巫塢豫奏短趙訛類椿搽邢啊京掛叛理國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法特征向量的計算int *findNext(String P) / 計算向量N int m = P.length(); / m為模板P的長度 assert( m 0); / 若m0，退出 int *next = new intm; / 動態(tài)存儲區(qū)開辟整數(shù)數(shù)組 assert( next != 0); / 若開辟存儲區(qū)域失敗，退出 next0 = -1;int i = 0; int k = -1; while (i = 0 & P i != P

32、k) k= nextk;i+; k+;nexti = k; return next;i012345PjabacabNj-100101驟賬輿凳襟肋胚嚇汞幽主展崎溜刑份杯瞧愈仙第饅忱騾火幻去窯嗅耀菇審國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法特征向量的計算：優(yōu)化版?當(dāng) j = 0時，令nextj = -1其實，若Pk = Pj ，則有pk Tj；此時應(yīng)再右移，使 Pnextk與 Tj 比較，故 第2步可進一步優(yōu)化為： if (Pk = Pj) nextj = nextk; else nextj = k;j012345PjabacabNj-10-11-10髓善稱沒咎沽壟斗誨披額炳輝頻赤

33、鳳自箍抬弱勁隘行祈能醒蕪舔蛙滌押羔國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法特征向量的計算：優(yōu)化版int *findNext(String P) int i = 0; int k = -1; int m = P.length(); / m為字符串P的長度 assert(m 0); / 若m0，退出 int *next = new intm; / 動態(tài)存儲區(qū)開辟整數(shù)數(shù)組assert(next != 0); / 若開辟存儲區(qū)域失敗，退出 next0 = -1;while (i = 0 & Pi != Pk) / 求最大首尾子串k = nextk;i+; k+;if (Pi = Pk

34、) nexti = nextk;/ Pi和Pk相等，優(yōu)化else nexti = k;/ 不需要優(yōu)化，就是位置i的首尾子串長度return next;黃爵勿諾摧鉗恤烽族淌亦簿頤遷炸博芯儀掂邊促垃蒼拆鋁痞畦奄漸扒顧唬國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法特征向量計算示例iknextP-0-1-1abacab-10-1,0abacab-1-20-1,0,-1abacab-31-1,0,-1,1abacab-1-40-1,0,-1,1,-1abacab-51-1,0,-1,1,-1,0abacab0abacab菩較拌杉亭礁葫咕肩蓉摹鈕煤暢受吝寄浦剛硯毯揭磷狡秀誠厭惱紙版嗽瑟國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法國家級精品課程數(shù)據(jù)結(jié)構(gòu)與算法KMP模式匹配算法int KMPStrMatching(String T, String P, int *N) int i = 0