數(shù)據(jù)結(jié)構(gòu)與算法字符串

1、數(shù)據(jù)結(jié)構(gòu)與算法第三章 字符串,主講人 張銘http://db.pku.edu.cn/mzhang/dsmzhang@db.pku.edu.cn北京大學(xué)信息科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)與信息系統(tǒng)研究所?版權(quán)所有，轉(zhuǎn)載或翻印必究,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 2,主要內(nèi)容,3.1 字符串抽象數(shù)據(jù)類型3.2

2、字符串的存儲(chǔ)結(jié)構(gòu)和類定義3.3 字符串運(yùn)算的算法實(shí)現(xiàn)3.4 字符串的模式匹配,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 3,3.1字符串抽象數(shù)據(jù)類型,3.1.1 基本概念3.1.2 String抽象數(shù)據(jù)類型,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

3、 Page 4,3.1.1 基本概念,字符串，由0個(gè)或多個(gè)字符的順序排列所組成的復(fù)合數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱“串”。串的長(zhǎng)度：一個(gè)字符串所包含的字符個(gè)數(shù)?？沾洪L(zhǎng)度為零的串，它不包含任何字符內(nèi)容。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 5,3.1.1.1字符串常數(shù)和變量,字符串常數(shù)例如： "

4、;\n"字符串變量,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 6,3.1.1.2 字符,字符(char) ：組成字符串的基本單位 。在C和C＋＋中單字節(jié)（8 bits）采用ASCII碼對(duì)128個(gè)符號(hào)（字符集charset）進(jìn)行編碼,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

5、 Page 7,3.1.1.3 字符的編碼順序,為了字符串間比較和運(yùn)算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。其實(shí)大多數(shù)情況下就是字典序中文字符串有些特例，例如“筆劃”序,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

6、 Page 8,3.1.1.4 C++標(biāo)準(zhǔn)string,標(biāo)準(zhǔn)字符串：將C++的函數(shù)庫作為字符串?dāng)?shù)據(jù)類型的方案。例如：char S[M];串的結(jié)束標(biāo)記：'\0''\0'是ASCII碼中8位BIT全0碼，又稱為NULL符。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 9,3.1

7、.1.4 C++標(biāo)準(zhǔn)string(續(xù)),1. 串長(zhǎng)函數(shù) int strlen(char *s);2. 串復(fù)制 char *strcpy(char *s1, char*s2);3．串拼接 char *strcat(char *s1, char *s2);4．串比較 int strcmp(char *s1, char *s2);,北京大學(xué)信息學(xué)院 ?版權(quán)所有

8、，轉(zhuǎn)載或翻印必究 Page 10,3.1.1.4 C++標(biāo)準(zhǔn)string(續(xù)),5．輸入和輸出函數(shù)6．定位函數(shù) char *strchr(char *s, char c);7．右定位函數(shù) char *strrchr(char *s, char c);,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

9、 Page 11,3.1.1.4 C++標(biāo)準(zhǔn)string(續(xù)),,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 12,3.1.2 String抽象數(shù)據(jù)類型,字符串類（class String）：不采用char S[M]的形式而采用一種動(dòng)態(tài)變長(zhǎng)的存儲(chǔ)結(jié)構(gòu)。,北京大學(xué)信息學(xué)院

10、 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 13,3.1.2 String抽象數(shù)據(jù)類型(續(xù)),,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 14,,,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

11、 Page 15,,,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 16,3.1.2.3 賦值算子、拼接算子和比較算子,賦值算子＝拼接算子＋比較算子 >= != 和 ==,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

12、 Page 17,3.1.2.4 輸入輸出算子>,輸入算子>>輸出算子<<,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 18,3.1.2.5 處理子串(Substring)的函數(shù),簡(jiǎn)稱“子串函數(shù)”提取子串插入子串尋找子串刪

13、除子串…,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 19,3.1.2.6 字符串中的字符,重載下標(biāo)算子[] char& operator[] (int n);按字符定位下標(biāo) int Find(char c,int start);反向?qū)ふ遥ㄎ晃膊砍霈F(xiàn)的字符 int FindLast(ch

14、ar c);,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 20,3.2 字符串的存儲(chǔ)結(jié)構(gòu)和類定義,3.2.1字符串的順序存儲(chǔ)3.2.2字符串類class String的存儲(chǔ)結(jié)構(gòu),北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Pag

15、e 21,3.2.1字符串的順序存儲(chǔ),對(duì)于串長(zhǎng)變化不大的字符串，可以有三種處理方案：（1）用S[0]作為記錄串長(zhǎng)的存儲(chǔ)單元。缺點(diǎn)：限制了串的最大長(zhǎng)度不能超過256。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 22,3.2.1字符串的順序存儲(chǔ)(續(xù)),（2）為存儲(chǔ)串的長(zhǎng)度，另辟一個(gè)存儲(chǔ)的地方。缺點(diǎn)：串的最大長(zhǎng)度一般是靜態(tài)給

16、定的，不是動(dòng)態(tài)申請(qǐng)數(shù)組空間。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 23,3.2.1字符串的順序存儲(chǔ)(續(xù)),（3）用一個(gè)特殊的末尾標(biāo)記'\0'。例如：C++語言的string函數(shù)庫（＃include ）采用這一存儲(chǔ)結(jié)構(gòu)。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

17、 Page 24,3.2.2 字符串類class String的存儲(chǔ)結(jié)構(gòu),抽取子串函數(shù) 例如： String s1 = "value-"; s2 = s1.Substr(2,3); 上述語句涉及的存儲(chǔ)形式如下頁所示。,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

18、 Page 25,3.2.2 字符串類class String的存儲(chǔ)結(jié)構(gòu)(續(xù)),,,,,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 26,3.2.2 字符串類class String的存儲(chǔ)結(jié)構(gòu)(續(xù)),微軟VC＋＋的CString類介紹自動(dòng)的動(dòng)態(tài)存儲(chǔ)管理，串的最大長(zhǎng)度不超過2GB 容器型不必使用ne

19、w和delete 使用特點(diǎn)：變量申明CString s6( 'x', 6 ); // s6 = "xxxxxx"CString city = "Philadelphia"; // 串常數(shù)作為初值賦值語句s1 = s2 = "hi there";變量比較 if( s1 == s2 ) 方法調(diào)用 s1.MakeUpper();

20、 內(nèi)部字符比較 if( s2[0] == 'h' ),,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 27,3.3 字符串運(yùn)算的算法實(shí)現(xiàn),1. 串長(zhǎng)函數(shù) int strlen(char *s);2. 串復(fù)制 char *strcpy(char *s1, char*s2);3．串拼接

21、 char *strcat(char *s1, char *s2);4．串比較 int strcmp(char *s1, char *s2);,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 28,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn),【算法3-1 】字符串的復(fù)制char *strcpy(char *d, cha

22、r *s){ //這個(gè)程序的毛病是，如果字符串s比字符串d要長(zhǎng)，//這個(gè)程序沒有檢查拷貝出界，沒有報(bào)告錯(cuò)誤。//可能會(huì)造成d的越界 int i =0; while (s[i] != '\0') { d[i] = s[i]; i++; } d[i] = '\0'; return d;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或

23、翻印必究 Page 29,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3-2 】字符串的比較int strcmp( char *d, char *s){ int i =0; while (s[i] != '\0' && d[i] != '\0' ) { if (d[i] > s[i])

24、 return 1; else if (d[i] < s[i]) return -1;,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 30,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),i ++; }if( d[i] = ='\0' && s[i] != &

25、#39;\0') return -1;else if (s[i] = = '\0'&& d[i] != '\0') return 1;return 0;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 31,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算

26、法3-3 】求字符串的長(zhǎng)度int strlen(char d[]){ int i =0; while (d[i] != 0) i++; return i;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 32,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3- 4 】尋找字符char * strchr

27、(char *d , char ch){ //按照數(shù)組指針d依次尋找字符ch，//如果找到ch，則將指針位置返回，//如果沒有找到ch，則為0值。i = 0;,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 33,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),//循環(huán)跳過那些不是ch的字符while (d[i] != 0 &

28、amp;& d[i] != ch ) i++; //當(dāng)本串不含字符ch，則在串尾結(jié)束； //當(dāng)成功尋找到ch，返回該位置指針if (d[i] = = 0) return 0; else return &d[i] ;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 34,3

29、.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3-5 】反向?qū)ふ易址鹀har * strrchr(char *d , char ch){ //按照數(shù)組指針d，從其尾部反著尋找字符ch， //如果找到ch，則將指針位置返回， //如果沒有找到ch，則為0值。 i = 0; //找串尾 while (d[i] != '\0' )i++;,北京大學(xué)信息學(xué)院

30、 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 35,3.3.1 C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù)),//循環(huán)跳過那些不是ch的字符while (i >= 0 && d[i] != ch ); //當(dāng)本串不含字符ch，則在串尾結(jié)束； //當(dāng)成功尋找到ch，返回該位置指針if (i < 0) return 0; el

31、se return &d[i] ; },北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 36,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3-7 】創(chuàng)建算子(constructor)String::String(char *s){ //先要確定新創(chuàng)字符串實(shí)際需要的存儲(chǔ)空間，s的類

32、//型為(char *)，作為新創(chuàng)字符串的初值。確定 //s的長(zhǎng)度，用標(biāo)準(zhǔn)字符串函數(shù)strlen(s)計(jì)算長(zhǎng)度size = strlen(s) ; //然后，在動(dòng)態(tài)存儲(chǔ)區(qū)域開辟一塊空間，用于存 //儲(chǔ)初值s，把結(jié)束字符也包括進(jìn)來str ＝ new char [size＋1];,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

33、 Page 37,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//開辟空間不成功時(shí)，運(yùn)行異常，退出assert(str != '\0'); //用標(biāo)準(zhǔn)字符串函數(shù)strcpy，將s完全 //復(fù)制到指針str所指的存儲(chǔ)空間strcpy( str, s );},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

34、 Page 38,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3-8 】銷毀算子（destructor）String::~String(){ //必須釋放動(dòng)態(tài)存儲(chǔ)空間delete [] str;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 39,3.3.2 String串運(yùn)算的實(shí)現(xiàn)

35、(續(xù)),【算法3-9】拼接算子String String::operator+ (String& s){ //把字符串s和本實(shí)例拼接成為一個(gè)長(zhǎng)串返回String temp; //創(chuàng)建一個(gè)串tempint len; //準(zhǔn)備工作，計(jì)算拼接后的長(zhǎng)串的長(zhǎng)度len = size + s.size; //把temp串創(chuàng)建時(shí)申請(qǐng)的存儲(chǔ)空間全部釋放delete [] temp.str

36、; //準(zhǔn)備工作，開辟空間，為存放長(zhǎng)串之用temp.str= new char [len+1];,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 40,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//若開辟動(dòng)態(tài)存儲(chǔ)空間不成功，則退出assert(temp.str!= 0)；temp.size= len;

37、//字符串str（以’\0’結(jié)尾）存到tempstrcpy(temp.str, str); //再把參數(shù)s的str和本實(shí)例的str拼接為長(zhǎng)串strcat(temp.str, s.str); return temp;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 41,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù))

38、,【算法3-10】賦值算子String String::operator= (String& s){ //參數(shù)s將被賦值到本串//若本串的串長(zhǎng)和s的串長(zhǎng)不同，則應(yīng)該釋放本串的//str存儲(chǔ)空間，并開辟新的空間if(size != s.size){ delete [] str ; //釋放原存儲(chǔ)空間 str = new char [s.size+1];,北京大學(xué)信息學(xué)院

39、 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 42,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出正常運(yùn)行 assert(str != 0)； size = s.size;}strcpy(str , s.str );//返回本實(shí)例，作為String類的一個(gè)實(shí)例return *this;},北京大學(xué)信息學(xué)院

40、 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 43,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法3-11】抽取子串函數(shù)String String::Substr(int index , int count ){ //取出一個(gè)子串返回，自下標(biāo)index開始，長(zhǎng)度為count int i; //本串自下標(biāo)index開始向

41、右數(shù)直到串尾，長(zhǎng)度為leftint left = size – index ; String temp;char *p, *q; //若下標(biāo)index值太大，超過本串實(shí)際串長(zhǎng)，則返回空串if(index >= size) // 注意不是 index >= size - 1 return temp;,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

42、 Page 44,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//若count超過自index以右的實(shí)際子串長(zhǎng)度， // 則把count變小if(count > left ) count = left;//釋放原來的存儲(chǔ)空間delete [] temp.str; //張銘注釋：注意此語句！//若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出temp.str = ne

43、w char [count+1]; assert(temp.str != 0)； //p的內(nèi)容是一個(gè)指針， //指向目前暫無內(nèi)容的字符數(shù)組的首字符處p = temp.str;,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 45,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//q的內(nèi)容是一個(gè)指針， //

44、指向本實(shí)例串的str數(shù)組的下標(biāo)index字符q = &str[index]; //用q指針取出它所指的字符內(nèi)容后，指針加1 // 用p該指針?biāo)傅淖址麊卧邮芸截?，該指針也?for (i =0; i < count; i++) *p++ = *q++; //循環(huán)結(jié)束后，讓temp.str的結(jié)尾為’\0’*p = 0; temp.size = count;return

45、temp;},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 46,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),【算法 3-12 】查找字符int String::Find(char c,int start){ //在本實(shí)例字符串尋找字符c，如果找到，則//將其下標(biāo)位置作為整數(shù)函數(shù)值返回，如果//c沒有找到，則為

46、負(fù)值。參數(shù)start是下標(biāo)，//從start下標(biāo)開始尋找c的工作,若start為//0，則從頭尋找int i = start;assert( i < size);,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 47,3.3.2 String串運(yùn)算的實(shí)現(xiàn)(續(xù)),//循環(huán)跳過那些不是c的字符while (str[i] !

47、= 0 && str[i] != c ) i++; //當(dāng)本串不含字符c，則尋找到串尾結(jié)束， //返回－1表示失??；當(dāng)成功尋找到c，返回它的 //下標(biāo)位置if (str[i] == 0) // 注意：不要搞成“= =” return -1; else return i ; },北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

48、 Page 48,3.4 字符串的模式匹配,模式匹配(pattern matching)一個(gè)目標(biāo)對(duì)象S（字符串）一個(gè)模板（pattern）P（字符串）任務(wù)：用給定的模板P，在目標(biāo)字符串S中搜索與模板P全同的一個(gè)子串，并求出S中第一個(gè)和P全同匹配的子串（簡(jiǎn)稱為“配串”），返回其首字符位置。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

49、 Page 49,,S s0 s1 … sisi+1 si+2 … si+m-2 si+m-1 … sn-1 ‖‖ ‖ ‖ ‖ P p0 p1 p2 … pm -2 pm-1為使模式 P 與目標(biāo) S 匹配，必須滿足 p0 p1

50、 p2 …pm-1 = si si+1 si+2 … si+m-1,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 50,樸素模式匹配,S=ababababababb…P=abababb X abababb X abababb

51、 X abababb X abababb X abababb X abababb ?,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究

52、 Page 51,【算法3-13 】模式匹配原始算法（其一）,#include “String.h” // 不是 #includeint FindPat_1(String S, String P, int startindex) { // 從S末尾倒數(shù)一個(gè)模板長(zhǎng)度位置 int LastIndex = S.strlen() - P.strlen(); if (L

53、astIndex < startindex) return (-1); //g為S的游標(biāo)，用模板P和S第g位置子串比較， //若失敗則繼續(xù)循環(huán) for (int g= startindex; g <= LastIndex; g++) if ( P == S.Substr(g, P.strlen() )) return g; //若for循環(huán)

54、結(jié)束，則整個(gè)匹配失敗，返回值為負(fù)， return (-1);},北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 52,3.4.1 模式匹配原始算法(續(xù)),【算法3-13】模式匹配原始算法（其二）int FindPat_2(String S, String P,int startindex){ // 從S末尾倒數(shù)

55、一個(gè)模板長(zhǎng)度位置 int LastIndex = S.strlen() - P.strlen(); //開始匹配位置startindex的值過大，匹配無法成功 if (LastIndex < startindex) return (-1); // i 是指向S內(nèi)部字符的游標(biāo)， // j 是指向P內(nèi)部字符的游標(biāo) int i=startindex, j = 0;,北京大學(xué)信息學(xué)院

56、 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 53,3.4.1 模式匹配原始算法(續(xù)),//下面開始循環(huán)匹配while (i <LastIndex && j <=P.strlen() ) if( P[j] == S[i]) { i++; j++;} else

57、{ i = i - j + 1; j = 0; },北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 54,3.4.1 模式匹配原始算法(續(xù)),//如果匹配成功，則返回該S子串的開 //始位置；如果P和S匹配失敗，函數(shù) //返回值為負(fù) if ( j > P.

58、strlen()) // “>” 可以嗎？ return (i - 1); else return -1; },北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 55,3.4.1 樸素模式匹配 (糾錯(cuò)),【算法3-13】模式匹配原始算法（糾錯(cuò)）int FindPat_2(String S, S

59、tring P,int startindex){ // 從S末尾倒數(shù)一個(gè)模板長(zhǎng)度位置 int LastIndex = S.strlen() - P. strlen() ; //開始匹配位置startindex的值過大，匹配無法成功 if (LastIndex < startindex) return (-1); // i 是指向S內(nèi)部字符的游標(biāo)， // j 是指向P內(nèi)部字符的游

60、標(biāo) int i=startindex, j = 0;,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 56,3.4.1 樸素模式匹配糾錯(cuò)(續(xù)),//下面開始循環(huán)匹配while (i<S.strlen() && j<P.strlen() ) // “<=”呢？ if( P[j]

61、== S[i]) { i++; j++;} else { i = i - j + 1; j = 0; },錯(cuò)誤1：如果“i < LastIndex”，那么后面的就匹配不到。例如，abababababb abababb S.strlen()=11，P.strlen()=7，LastIndex

62、 = 4;“i = 4，j = 0”, 匹配‘a(chǎn)’，接著， “i = 5，j = 1”就進(jìn)行不了。,錯(cuò)誤2： 如果“j <=P.strlen()”，則P的結(jié)束符號(hào)‘\0’也拿來比較，除非正好匹配S的末端，否則出錯(cuò)！,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 57,3.4.1樸素模式匹配糾錯(cuò)(續(xù)),//如果匹配成

63、功，則返回該S子串的開 //始位置；如果P和S匹配失敗，函數(shù) //返回值為負(fù) if ( j >= P.strlen() ) // “>” 可以嗎？ return (i - j); else return -1; },錯(cuò)誤3： 如果“j >P.strlen”，其實(shí)匹配結(jié)束時(shí)，正好j==P.size （因?yàn)槠ヅ渥詈笠粋€(gè)字符后，還j++）出錯(cuò)！其實(shí) “j ==

64、 P.strlen” 就可以！,錯(cuò)誤4： return (i-1); 匹配完成后，i指向S中最后一個(gè)字符的下一位，減去匹配串的長(zhǎng)度，才是開始位。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 58,3.4.1 模式匹配原始算法(續(xù)),例如，aaaaaaaaaab aaaaaab分析假定

65、目標(biāo)S的長(zhǎng)度為n，模板P長(zhǎng)度為m， m≤n 在最壞的情況下，每一次循環(huán)都不成功，則一共要進(jìn)行比較（n-m+1）次每一次“相同匹配”比較所耗費(fèi)的時(shí)間，是P和S逐個(gè)字符比較的時(shí)間，最壞情況下，共m次。因此，整個(gè)算法的最壞時(shí)間開銷估計(jì)為O(m ? n)。,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 59,,例1， a a a

66、a a a a a a a b a a a a a a b ? a a a a a a b ¦ a a a a a a b例2， a b c d e f a b c d e f f a

67、b c d e f f ? a b c d e f f,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 60,KMP算法思想,S s0 s1 … si-j-1 si-j si-j+1 si-j+2 … si-2 s

68、i-1 si … sn-1 ‖ ‖ ‖ ‖ ‖ ? P p0 p1 p2 … pj-2 pj -1 pj 則有 si-j si-j+1 si-j+2 … si-1 = p0 p1 p2 …pj-1 (1) 如果 p0 p

69、1 …pj-2 ? p1 p2 …pj-1 (2) 則立刻可以斷定 p0 p1 …pj-2 ? si-j+1 si-j+2 … si-1 (樸素匹配的)下一趟一定不匹配，可以跳過去,北京大學(xué)信息學(xué)院 ?版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 61,,同樣，若 p0 p1 …pj-3

70、? p2 p3 …pj-1則再下一趟也不匹配，因?yàn)橛?p0 p1 …pj-3 ? si-j+2 si-j+3 … si-1直到對(duì)于某一個(gè)“k”值(首尾串長(zhǎng)度)，使得 p0 p1 …pk ? pj-k-1 pj-k …pj-1 且 p0 p1 …pk-1 = pj-k pj-k+1 …pj-1則 p0 p1 …pk-1 = si-

71、k si-k+1 … si-1 si ‖ ‖ ‖ ? pj-k pj-k+1 … pj-1 pj ‖ ‖ ‖ ?