數(shù)據(jù)結(jié)構(gòu)與算法第三章2013ppt課件

1、3.1 字符串抽象數(shù)據(jù)類型字符串抽象數(shù)據(jù)類型3.2 字符串的存儲(chǔ)結(jié)構(gòu)和類定義字符串的存儲(chǔ)結(jié)構(gòu)和類定義3.3 字符串運(yùn)算的算法實(shí)現(xiàn)字符串運(yùn)算的算法實(shí)現(xiàn)3.4 字符串的模式匹配字符串的模式匹配3.1字符串抽象數(shù)據(jù)類型字符串抽象數(shù)據(jù)類型3.1.1 基本概念基本概念3.1.2 String抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 3.1.1 基本概念 字符串：由0個(gè)或多個(gè)字符的順序排列所組成的復(fù)合數(shù)據(jù)結(jié)構(gòu)，簡稱“串”。串的長度：一個(gè)字符串所包含的字符個(gè)數(shù)。空串：長度為零的串，它不包含任何字符內(nèi)容。3.1.1.1字符串常數(shù)和變量字符串常數(shù)和變量 字符串常數(shù) 例如： n 字符串變量3.1.1.2 字符字符 字符(char

2、) ：組成字符串的基本單位。 在C和C中 單字節(jié)8 bits） 采用ASCII碼對(duì)128個(gè)符號(hào)字符集charset進(jìn)行編碼3.1.1.3 字符的編碼順序字符的編碼順序 為了字符串間比較和運(yùn)算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。 字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。 其實(shí)大多數(shù)情況下就是字典序 中文字符串有些特例，例如“筆劃序3.1.1.4 C+標(biāo)準(zhǔn)標(biāo)準(zhǔn)string 標(biāo)準(zhǔn)字符串：將C+的函數(shù)庫作為字符串?dāng)?shù)據(jù)類型的方案。 例如：char SM; 串的結(jié)束標(biāo)記：0 0是ASCII碼中8位BIT全0碼，又稱為NULL符。3.1.1.4 C+標(biāo)準(zhǔn)標(biāo)準(zhǔn)string(

3、續(xù)續(xù)) 1. 串長函數(shù)串長函數(shù) int strlen(char *s); 2. 串復(fù)制串復(fù)制 char *strcpy(char *s1, char*s2); 3串拼接串拼接 char *strcat(char *s1, char *s2); 4串比較串比較 int strcmp(char *s1, char *s2);3.1.1.4 C+標(biāo)準(zhǔn)標(biāo)準(zhǔn)string(續(xù)續(xù)) 5輸入和輸出函數(shù) 6定位函數(shù) char *strchr(char *s, char c); 7右定位函數(shù) char *strrchr(char *s, char c);3.1.1.4 C+標(biāo)準(zhǔn)標(biāo)準(zhǔn)string(續(xù)續(xù))3.1.2

4、String抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 字符串類class String）： 不采用char SM的形式 而采用一種動(dòng)態(tài)變長的存儲(chǔ)結(jié)構(gòu)。class String /字符串類字符串類/它的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法使用了它的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法使用了C+標(biāo)準(zhǔn)標(biāo)準(zhǔn)string(簡稱標(biāo)準(zhǔn)簡稱標(biāo)準(zhǔn)串串),/為了區(qū)別為了區(qū)別,類類String所派生創(chuàng)建的實(shí)例對(duì)象所派生創(chuàng)建的實(shí)例對(duì)象,簡稱簡稱本串本串,或或?qū)崒?shí)例串例串/在程序首在程序首,要要#include 和和#include 及及/ 及及#include ，以及，以及#include /1.字符串的數(shù)據(jù)表示：字符串的數(shù)據(jù)表示：/字符串字符串S 通常用順序存放，用

5、數(shù)組通常用順序存放，用數(shù)組S存儲(chǔ)，元素的類型為存儲(chǔ)，元素的類型為char/字符串為變長，使用變量字符串為變長，使用變量size記錄串的當(dāng)前長度記錄串的當(dāng)前長度/ 2.使用變量訪問字符串：使用變量訪問字符串：/字符串變量能參與運(yùn)算字符串變量能參與運(yùn)算,例如例如S1 + S2表示兩個(gè)字符串首尾拼表示兩個(gè)字符串首尾拼接在一起接在一起/用數(shù)組用數(shù)組str存儲(chǔ)字符串，在內(nèi)部可以用存儲(chǔ)字符串，在內(nèi)部可以用stri訪問串的第訪問串的第i個(gè)個(gè)字符字符,/ 3.字符串類的運(yùn)算集：請(qǐng)參看下面的成員函數(shù)字符串類的運(yùn)算集：請(qǐng)參看下面的成員函數(shù)private: char *str; /私有的指針變量，用于指向存儲(chǔ)向量私

6、有的指針變量，用于指向存儲(chǔ)向量strsize+1 int size； /本串的當(dāng)前實(shí)際長度本串的當(dāng)前實(shí)際長度public:String(char *s = “”); /創(chuàng)建一個(gè)空的字符串創(chuàng)建一個(gè)空的字符串String(char *s); / 創(chuàng)建新字符串，并將標(biāo)準(zhǔn)字符串創(chuàng)建新字符串，并將標(biāo)準(zhǔn)字符串s拷貝為初值拷貝為初值String(const String &copy);/拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)String() / 銷毀本串，從計(jì)算機(jī)存儲(chǔ)空間刪去本串銷毀本串，從計(jì)算機(jī)存儲(chǔ)空間刪去本串/下面是算子的定義，包括賦值算子下面是算子的定義，包括賦值算子 拼接算子拼接算子 和比較算子和比較算子

7、 等等const String& operator= (const char *s）；）； /賦值操作賦值操作=，標(biāo)準(zhǔn)串，標(biāo)準(zhǔn)串s拷貝到本串拷貝到本串const String& operator= (const String& s）; /賦值操作賦值操作=，串，串s復(fù)制到本串復(fù)制到本串String operator (char *s）;/拼接算子，本串拼接標(biāo)準(zhǔn)串拼接算子，本串拼接標(biāo)準(zhǔn)串sString operator (String& s）；）；/拼接算子，本串拼接串拼接算子，本串拼接串sfriend String operator+ (char *s1, St

8、ring& s）；）；/友函數(shù)作為拼接算子友函數(shù)作為拼接算子+ 其返回值是一個(gè)實(shí)例串其返回值是一個(gè)實(shí)例串,等于標(biāo)準(zhǔn)串等于標(biāo)準(zhǔn)串str拼接串拼接串s/關(guān)系算子，用于比較相等、大、小，例如bool operator (char *s）;/比較大小,本串小于標(biāo)準(zhǔn)串s則返回非0bool operator (String& s）;/比較大小，本串小于串s則返回非0friend bool operator和 (isteream& istr,String& s）；friend ostream& operator (osteream& ostr,String&a

9、mp; s）；/ 子串函數(shù)：插入子串、尋找子串、提取子串、刪除子串等，例如String Substr(int index，int count）; /它們的功能參見下文/串與字符函數(shù)：按字符定位等，例如int Find(char c,int start);/在本串中尋找字符c,從下標(biāo)start開始找,/ 尋找到c后,返回字符c在本串的下標(biāo)位置/其他函數(shù)：求串長、判空串、清為空串、int strlen(); /返回本串的當(dāng)前串長int IsEmpty(); /判本串為空串?void clear(); /清本串為空串char &operator(int x); /左操作數(shù)const char

10、 &operator(int x)const; /右操作數(shù);3.1.2.3 賦值算子、拼接算子賦值算子、拼接算子和比較算子和比較算子 賦值算子 拼接算子 比較算子 = !=和=3.1.2.4 輸入輸出算子輸入輸出算子 輸入算子 輸出算子3.1.2.5 處理子串處理子串(Substring)的函數(shù)的函數(shù) 簡稱“子串函數(shù)” 提取子串 插入子串 尋找子串 刪除子串 3.1.2.6 字符串中的字符字符串中的字符 重載下標(biāo)算子 char& operator (int n); 按字符定位下標(biāo) int Find(char c,int start); 反向?qū)ふ?，定位尾部出現(xiàn)的字符 int Fi

11、ndLast(char c);3.2 字符串的存儲(chǔ)結(jié)構(gòu)和類定義字符串的存儲(chǔ)結(jié)構(gòu)和類定義 3.2.2字符串類字符串類class String的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu) 3.2.1字符串的順序存儲(chǔ)字符串的順序存儲(chǔ)3.2.1字符串的順序存儲(chǔ)字符串的順序存儲(chǔ) 對(duì)于串長變化不大的字符串，可以有三種處理方案： （1用S0作為記錄串長的存儲(chǔ)單元。 缺點(diǎn)：限制了串的最大長度不能超過256。3.2.1字符串的順序存儲(chǔ)字符串的順序存儲(chǔ)(續(xù)續(xù))（2為存儲(chǔ)串的長度，另辟一個(gè)存儲(chǔ)的地方。 缺點(diǎn)：串的最大長度一般是靜態(tài)給定的，不是動(dòng)態(tài)申請(qǐng)數(shù)組空間。3.2.1字符串的順序存儲(chǔ)字符串的順序存儲(chǔ)(續(xù)續(xù))（3用一個(gè)特殊的末尾標(biāo)記0。

12、例如：C+語言的string函數(shù)庫（include ）采用這一存儲(chǔ)結(jié)構(gòu)。3.2.2 字符串類字符串類class String的存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu) 抽取子串函數(shù) 例如： String s1 = value-; s2 = s1.Substr(2,3); 上述語句涉及的存儲(chǔ)形式如下頁所示。3.2.2 字符串類字符串類class String的存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)(續(xù)續(xù))微軟VC的CString類介紹 自動(dòng)的動(dòng)態(tài)存儲(chǔ)管理，串的最大長度不超過2GB 容器型 不必使用new和delete 使用特點(diǎn)： 變量申明 CString s6( x, 6 ); / s6 = xxxxxx CString city =

13、Philadelphia; / 串常數(shù)作為初值 賦值語句 s1 = s2 = hi there; 變量比較if( s1 = s2 ) 方法調(diào)用s1.MakeUpper(); 內(nèi)部字符比較if( s20 = h )3.3 字符串運(yùn)算的算法實(shí)現(xiàn)字符串運(yùn)算的算法實(shí)現(xiàn) 1. 串長函數(shù)串長函數(shù) int strlen(char *s); 2. 串復(fù)制串復(fù)制 char *strcpy(char *s1, char*s2); 3串拼接串拼接 char *strcat(char *s1, char *s2); 4串比較串比較 int strcmp(char *s1, char *s2);3.3.1 C+標(biāo)準(zhǔn)串運(yùn)

14、算的實(shí)現(xiàn)標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)3.3.1 C+標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn) 【算法【算法3-1 】字符串的復(fù)制】字符串的復(fù)制 char *strcpy(char *d, char *s) /這個(gè)程序的毛病是，如果字符串這個(gè)程序的毛病是，如果字符串s比字符串比字符串d要長，要長， /這個(gè)程序沒有檢查拷貝出界，沒有報(bào)告錯(cuò)誤。這個(gè)程序沒有檢查拷貝出界，沒有報(bào)告錯(cuò)誤。 /可能會(huì)造成可能會(huì)造成d的越界的越界 int i =0; while (si != 0) di = si; i+; di = 0; return d; 3.3.1 C+標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)標(biāo)準(zhǔn)串

15、運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-2 】字符串的比較 int strcmp( char *d, char *s) int i =0; while (si != 0 & di != 0 ) if (di si) return 1; else if (di =0 & di != ch ) i-;/當(dāng)本串不含字符當(dāng)本串不含字符ch，則在串尾結(jié)束；，則在串尾結(jié)束；/當(dāng)成功尋找到當(dāng)成功尋找到ch，返回該位置指針，返回該位置指針if (i0) return 0;else return &di ;3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-7 】創(chuàng)建算子(cons

16、tructor) String:String(char *s) /先要確定新創(chuàng)字符串實(shí)際需要的存儲(chǔ)空間，s的類 /型為(char *)，作為新創(chuàng)字符串的初值。確定 /s的長度，用標(biāo)準(zhǔn)字符串函數(shù)strlen(s)計(jì)算長度 size = strlen(s) ; /然后，在動(dòng)態(tài)存儲(chǔ)區(qū)域開辟一塊空間，用于存 /儲(chǔ)初值s，把結(jié)束字符也包括進(jìn)來 str new char size1;/開辟空間不成功時(shí)，運(yùn)行異常，退出開辟空間不成功時(shí)，運(yùn)行異常，退出assert(str != 0);/用標(biāo)準(zhǔn)字符串函數(shù)用標(biāo)準(zhǔn)字符串函數(shù)strcpy，將，將s完全完全/復(fù)制到指針復(fù)制到指針str所指的存儲(chǔ)空間所指的存儲(chǔ)空間str

17、cpy( str, s );拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)String: String(const String &copy); size=copy.size ; str new char size1; assert(str != 0); strcpy( str, copy.str );3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-8 】銷毀算子destructor） String:String() /必須釋放動(dòng)態(tài)存儲(chǔ)空間 delete str; 3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法【算法3-9】拼接算子】拼接算子 String String

18、:operator+ (String& s) /把字符串把字符串s和本實(shí)例拼接成為一個(gè)長串返回和本實(shí)例拼接成為一個(gè)長串返回 String temp; /創(chuàng)建一個(gè)串創(chuàng)建一個(gè)串temp int len; /準(zhǔn)備工作，計(jì)算拼接后的長串的長度準(zhǔn)備工作，計(jì)算拼接后的長串的長度 len = size + s.size; /把把temp串創(chuàng)建時(shí)申請(qǐng)的存儲(chǔ)空間全部釋放串創(chuàng)建時(shí)申請(qǐng)的存儲(chǔ)空間全部釋放 delete temp.str; /準(zhǔn)備工作，開辟空間，為存放長串之用準(zhǔn)備工作，開辟空間，為存放長串之用 temp.str= new char len+1;/若開辟動(dòng)態(tài)存儲(chǔ)空間不成功，則退出若開辟動(dòng)態(tài)存儲(chǔ)空

19、間不成功，則退出assert(temp.str!= 0)；temp.size= len;/字符串字符串str以以0結(jié)尾存到結(jié)尾存到tempstrcpy(temp.str, str);/再把參數(shù)再把參數(shù)s的的str和本實(shí)例的和本實(shí)例的str拼接為長串拼接為長串strcat(temp.str, s.str);return temp;3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-10】賦值算子 const String& String:operator= (const String& s) /參數(shù)s將被賦值到本串 /若本串的串長和s的串長不同，則應(yīng)該釋放本串的

20、/str存儲(chǔ)空間，并開辟新的空間 if(this != &s) delete str ; /釋放原存儲(chǔ)空間 str = new char s.size+1;/若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出正常運(yùn)若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出正常運(yùn)行行assert(str != 0)；size = s.size;strcpy(str , s.str ); /返回本實(shí)例，作為返回本實(shí)例，作為String類的一個(gè)實(shí)例類的一個(gè)實(shí)例return *this;bool String: operator (String& s） return strcmp(str,s.str) (isteream&

21、istr,String& s） char temp1000;istrtemp;s=temp;return istr;friend ostream& String: operator (osteream& ostr,String& s） ostr temp; delete s.str; s.size=strlen(temp); s.str=new chars.size+1; assert(s.str !=0); strcpy(s.str,temp); return istr;3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-11】抽取子串函數(shù) S

22、tring String:Substr(int index , int count ) /取出一個(gè)子串返回，自下標(biāo)index開始，長度為count int i; /本串自下標(biāo)index開始向右數(shù)直到串尾，長度為left int left = size index ; String temp; char *p, *q; /若下標(biāo)index值太大，超過本串實(shí)際串長，則返回空串 if(index = size) return temp;/若若count超過自超過自index以右的實(shí)際子串長度，以右的實(shí)際子串長度，/ 則把則把count變小變小if(count left )count = left;/

23、釋放原來的存儲(chǔ)空間釋放原來的存儲(chǔ)空間delete temp.str; /若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出若開辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出temp.str = new char count+1;assert(temp.str != 0)；/p的內(nèi)容是一個(gè)指針，的內(nèi)容是一個(gè)指針，/指向目前暫無內(nèi)容的字符數(shù)組的首字符處指向目前暫無內(nèi)容的字符數(shù)組的首字符處p = temp.str;/q的內(nèi)容是一個(gè)指針，的內(nèi)容是一個(gè)指針，/指向本實(shí)例串的指向本實(shí)例串的str數(shù)組的下標(biāo)數(shù)組的下標(biāo)index字符字符q = &strindex;/用用q指針取出它所指的字符內(nèi)容后，指針加指針取出它所指的字符內(nèi)容后，指針加1

24、/ 用用p該指針?biāo)傅淖址麊卧邮芸截悾撝羔樢苍撝羔標(biāo)傅淖址麊卧邮芸截?，該指針也加?for (i =0; i count; i+)*p+ = *q+;/循環(huán)結(jié)束后，讓循環(huán)結(jié)束后，讓temp.str的結(jié)尾為的結(jié)尾為0*p = 0;temp.size = count;return temp;3.3.2 String串運(yùn)算的實(shí)現(xiàn)串運(yùn)算的實(shí)現(xiàn)(續(xù)續(xù)) 【算法3-12 】查找字符 int String:Find(char c,int start) /在本實(shí)例字符串尋找字符c，如果找到，那么 /將其下標(biāo)位置作為整數(shù)函數(shù)值返回，假如 /c沒有找到，則為負(fù)值。參數(shù)start是下標(biāo)， /從start下標(biāo)

25、開始尋找c的工作,若start為 /0，則從頭尋找 int i = start; assert( i =0&x=0&xsize);return strx;3.4 字符串的模式匹配字符串的模式匹配 模式匹配(pattern matching) 一個(gè)目標(biāo)對(duì)象S字符串） 一個(gè)模板patternP字符串） 任務(wù)：用給定的模板P，在目標(biāo)字符串S中搜索與模板P全同的一個(gè)子串，并求出S中第一個(gè)和P全同匹配的子串簡稱為“配串”），返回其首字符位置。 s=“ababcabcacbab” t=“abcac” i01234tjabcacNj-10001Nj-100-11樸素模式匹配：例如樸素模式匹配

26、：例如l把模式與目標(biāo)逐一進(jìn)行比較首位置開始），直到碰到不匹配的字符把模式與目標(biāo)逐一進(jìn)行比較首位置開始），直到碰到不匹配的字符為止模式右移一位再次開始匹配）為止模式右移一位再次開始匹配）l算法可在第一個(gè)匹配或是目標(biāo)的結(jié)束處停止算法可在第一個(gè)匹配或是目標(biāo)的結(jié)束處停止abacababacababacaacabcabacabaa01234587691011121314151617abacababacababacababacababacab樸素模式匹配(Brute Force)3.4.1 模式匹配原始算法模式匹配原始算法(續(xù)續(xù))_BF算法算法 【算法3-13 】模式匹配原始算法其一） #include

27、#include int FindPat_1(String S, String P, int startindex) / 從S末尾倒數(shù)一個(gè)模板長度位置 int LastIndex = S.strlen() - P.strlen(); /開始匹配位置startindex的值過大，匹配無法成功 if (LastIndex startindex) return (-1);/g為為S的游標(biāo)，用模板的游標(biāo)，用模板P和和S第第g位置子串比較，位置子串比較，若失若失/敗則繼續(xù)循環(huán)敗則繼續(xù)循環(huán)for (int g= startindex; g = LastIndex; g+) if ( P = S.Subst

28、r(g, P.strlen()return g;/若若for循環(huán)結(jié)束，則整個(gè)匹配失敗，返回值為負(fù)，循環(huán)結(jié)束，則整個(gè)匹配失敗，返回值為負(fù)，return (-1);【算法3-13】模式匹配原始算法（其二）/ 從從S末尾倒數(shù)一個(gè)模板長度位置末尾倒數(shù)一個(gè)模板長度位置int LastIndex = S. strlen() - P. strlen();/開始匹配位置開始匹配位置startindex的值過大，匹配無法成功的值過大，匹配無法成功if (LastIndex startindex)return (-1);/ i 是指向是指向S內(nèi)部字符的游標(biāo)，內(nèi)部字符的游標(biāo)，/ j 是指向是指向P內(nèi)部字符的游標(biāo)內(nèi)部

29、字符的游標(biāo)int i=startindex, j = 0;/下面開始循環(huán)匹配下面開始循環(huán)匹配while (i S. strlen() & j = P. strlen() /return (i - j);elsereturn -1;樸素匹配算法：效率分析樸素匹配算法：效率分析 假定目標(biāo)假定目標(biāo)T的長度為的長度為n，模式，模式P長度為長度為m，且且 m n 在最壞的情況下，每一次循環(huán)都不成功，在最壞的情況下，每一次循環(huán)都不成功，則一共要進(jìn)行比較則一共要進(jìn)行比較n-m+1次次 每一次每一次“相同匹配比較所耗費(fèi)的時(shí)間，相同匹配比較所耗費(fèi)的時(shí)間，是是P和和T逐個(gè)字符比較的時(shí)間，最壞情況逐個(gè)字符比

30、較的時(shí)間，最壞情況下，共下，共m次次 因而，整個(gè)算法的最壞時(shí)間開銷估計(jì)為因而，整個(gè)算法的最壞時(shí)間開銷估計(jì)為O(mn)樸素匹配算法：最差情況樸素匹配算法：最差情況 模式與目標(biāo)的每一個(gè)長度為模式與目標(biāo)的每一個(gè)長度為m的子串進(jìn)行比較的子串進(jìn)行比較l目標(biāo)形如目標(biāo)形如an, 模模式形如式形如am-1bl總比較次數(shù)：總比較次數(shù)：lO(n-m+1)l時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：lO(mn)AAAAAAAAAAAAAAAAAAAAAAAAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較AAAAAAAAAAAAAAA

31、AAAAAAA AAAAB 5次比較AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比較樸素匹配算法：樸素匹配算法：最佳情況最佳情況-沒找到模式?jīng)]找到模式 總是在第一個(gè)字符上不匹配總是在第一個(gè)字符上不匹配l總比較次數(shù)：總比較次數(shù)：ln-m+1l時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：lO(n)AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比較AAAAAAAAAAAAAAAAAAAAAH 1

32、次比較 OOOOH樸素模式匹配算法：樸素模式匹配算法：最佳情況最佳情況-找到模式找到模式 在目標(biāo)的前在目標(biāo)的前m個(gè)位置上找到模式，設(shè)個(gè)位置上找到模式，設(shè) m = 5l總比較次數(shù)：總比較次數(shù)：ml時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(m)AAAAAAAAAAAAAAAAAAAAABAAAAA 5次比較次比較 樸素算法的問題：回溯樸素算法的問題：回溯 樸素算法之所以效率不高的原樸素算法之所以效率不高的原因在于匹配過程中目標(biāo)串有回因在于匹配過程中目標(biāo)串有回溯，且這些回溯并非必要溯，且這些回溯并非必要 e.g., 由由1可知：可知： P5 T5， P0=T0, P1 = T1,同時(shí)由同時(shí)由 P0 P1可得知可得

33、知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 1P5 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 2P0 T1 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 3P1 T3

34、 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.無回溯匹配算法無回溯匹配算法關(guān)鍵在于匹配過程中，一旦關(guān)鍵在于匹配過程中，一旦Pi 和和Tj比較不等時(shí)，比較不等時(shí)，即即 substr(P,1,i-1) = substr(T, j-i+1,i-1) 且且Pi Tj 要能立即確定右移的位數(shù)和繼續(xù)比較的字符，要能立即確定右移的位數(shù)和繼續(xù)比較的字符，即該用即該用P中的哪個(gè)字符和中的哪個(gè)字符和Tj進(jìn)行比較？進(jìn)行比較？ 如何定位如何定位? 保留之前比較的結(jié)果保留之前比較的結(jié)果?若把這個(gè)字符記為若把這個(gè)字符記為Pk，顯然有，顯然有k 0

35、，k 0 且且 Pj = Pk ，則，則nj+1 = k+1；當(dāng)當(dāng)k 0, 且且P j Pk 時(shí)，則令時(shí)，則令k = nk，并讓，并讓 步步驟驟3循環(huán)直到條件不滿足變?yōu)檠h(huán)直到條件不滿足變?yōu)镻 j = Pk 或或 k = -1）；）；當(dāng)當(dāng) k0 (此時(shí)，此時(shí)，k -1), 那么那么 nj1= 0。otherwise 0,existsk asuchif,1)-k.j-P(j 1)-P(0.k & jk0 :maxk0jfor1, j next對(duì)應(yīng)的求特征向量算法框架在在KMP快速模式匹配中，若用快速模式匹配中，若用ni表示第表示第i位的特征值，位的特征值，特征數(shù)特征數(shù)ni +1( -1

36、ni 0的的ni+1，假定已知前一位置沒有，假定已知前一位置沒有優(yōu)化以前的特征數(shù)優(yōu)化以前的特征數(shù) ni = k；2. 當(dāng)當(dāng)k =0，且，且Pi Pk 時(shí)，則令時(shí)，則令k = nk，并讓步驟，并讓步驟2循循環(huán)直到條件不滿足變?yōu)榄h(huán)直到條件不滿足變?yōu)镻i = =Pk ，或上一步驟，或上一步驟k = 0而導(dǎo)致而導(dǎo)致k = nk步驟后步驟后k = -1了）；了）；3. ni+1 = k+1這是沒有優(yōu)化以前的特征數(shù)，在優(yōu)化前這是沒有優(yōu)化以前的特征數(shù)，在優(yōu)化前傳到第一步用于計(jì)算下一個(gè)特征值）；傳到第一步用于計(jì)算下一個(gè)特征值）；4. 若若Pi+1 = =Pk+1 ，則，則ni+1 = nk+1此步驟為優(yōu)此步驟

37、為優(yōu)化）?；Ｒ话惆涯Ｊ降牡谝粋€(gè)字符的特征數(shù)設(shè)置為一般把模式的第一個(gè)字符的特征數(shù)設(shè)置為-1，以盡可能地減少，以盡可能地減少冗余比較：冗余比較： 特征向量的計(jì)算特征向量的計(jì)算 求求p0, p1,pj-1 中最大相同的前綴與后中最大相同的前綴與后綴的長度綴的長度t nextj = t 計(jì)算計(jì)算nextj時(shí)充分利用了位置時(shí)充分利用了位置j之前的各之前的各個(gè)字符的個(gè)字符的next值值特征向量的計(jì)算特征向量的計(jì)算int *findNext(String P) / 計(jì)算向量計(jì)算向量N int m = P.length(); / m為模板為模板P的長度的長度 assert( m 0); / 若若m0，退出

38、，退出 int *next = new intm; / 動(dòng)態(tài)存儲(chǔ)區(qū)開辟整數(shù)數(shù)組動(dòng)態(tài)存儲(chǔ)區(qū)開辟整數(shù)數(shù)組 assert( next != 0); / 若開辟存儲(chǔ)區(qū)域失敗，退出若開辟存儲(chǔ)區(qū)域失敗，退出 next0 = -1;int i = 0; int k = -1; while (i = 0 & P i != Pk) k= nextk;i+; k+;nexti = k; return next;i012345PjabacabNj-100101特征向量的計(jì)算：優(yōu)化版特征向量的計(jì)算：優(yōu)化版?當(dāng)當(dāng) j = 0時(shí)，令時(shí)，令nextj = -1其實(shí)，若其實(shí)，若Pk = Pj ，則有，則有pk Ti；

39、此時(shí)應(yīng)再右移，使；此時(shí)應(yīng)再右移，使 Pnextk與與 Tj 比較，故比較，故 第第2步可進(jìn)一步優(yōu)化為：步可進(jìn)一步優(yōu)化為： if (Pk = Pj) nextj = nextk; else nextj = k;j012345PjabacabNj-100101Nj-10-11-10特征向量的計(jì)算：優(yōu)化版特征向量的計(jì)算：優(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; / 動(dòng)態(tài)存儲(chǔ)區(qū)開辟整數(shù)數(shù)組動(dòng)態(tài)存儲(chǔ)區(qū)開辟整數(shù)數(shù)組assert(next != 0); / 若開辟存儲(chǔ)區(qū)域失敗，退出若開辟存儲(chǔ)區(qū)域失敗，退出 next0 = -1;while (i = 0 & Pi != Pk) / 求最大首尾子串求最大首尾子串k = nextk;i+; k+;if (Pi = Pk ) nexti = nextk;/ Pi和和Pk相等，優(yōu)化相等，優(yōu)化else nexti = k;/ 不需要優(yōu)化，就是位置不需要優(yōu)化，就是位置i的首尾子串長度的首尾子串長度return next;特征向量計(jì)算示例特征向量計(jì)算示例iknextP-0