北大信息院數(shù)據(jù)結(jié)構(gòu)ds 03string

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

第三章字符串主講人張銘

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)與信息系統(tǒng)研究所，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2主要內(nèi)容3.1字符串抽象數(shù)據(jù)類型3.2字符串的存儲(chǔ)結(jié)構(gòu)和類定義3.3字符串運(yùn)算的算法實(shí)現(xiàn)3.4字符串的模式匹配北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page33.1字符串抽象數(shù)據(jù)類型3.1.1基本概念3.1.2String抽象數(shù)據(jù)類型北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page43.1.1基本概念字符串，由0個(gè)或多個(gè)字符的順序排列所組成的復(fù)合數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱“串”。串的長(zhǎng)度：一個(gè)字符串所包含的字符個(gè)數(shù)。空串：長(zhǎng)度為零的串，它不包含任何字符內(nèi)容。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page53.1.1.1字符串常數(shù)和變量字符串常數(shù)例如："\n"字符串變量北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page63.1.1.2字符字符(char)：組成字符串的基本單位。在C和C＋＋中單字節(jié)（8bits）采用ASCII碼對(duì)128個(gè)符號(hào)（字符集charset）進(jìn)行編碼北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page73.1.1.3字符的編碼順序?yàn)榱俗址g比較和運(yùn)算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。其實(shí)大多數(shù)情況下就是字典序中文字符串有些特例，例如“筆劃”序北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page83.1.1.4C++標(biāo)準(zhǔn)string標(biāo)準(zhǔn)字符串：將C++的<string.h>函數(shù)庫(kù)作為字符串?dāng)?shù)據(jù)類型的方案。例如：charS[M];串的結(jié)束標(biāo)記：'\0''\0'是ASCII碼中8位BIT全0碼，又稱為NULL符。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page93.1.1.4C++標(biāo)準(zhǔn)string(續(xù))1.串長(zhǎng)函數(shù)

intstrlen(char*s);2.串復(fù)制

char*strcpy(char*s1,char*s2);3．串拼接

char*strcat(char*s1,char*s2);4．串比較

intstrcmp(char*s1,char*s2);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page103.1.1.4C++標(biāo)準(zhǔn)string(續(xù))5．輸入和輸出函數(shù)6．定位函數(shù)

char*strchr(char*s,charc);7．右定位函數(shù)

char*strrchr(char*s,charc);

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page113.1.1.4C++標(biāo)準(zhǔn)string(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page123.1.2String抽象數(shù)據(jù)類型字符串類（classString）：不采用charS[M]的形式而采用一種動(dòng)態(tài)變長(zhǎng)的存儲(chǔ)結(jié)構(gòu)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page133.1.2String抽象數(shù)據(jù)類型(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page163.1.2.3賦值算子、拼接算子和比較算子賦值算子＝拼接算子＋比較算子<<=>>=!=和==北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page173.1.2.4輸入輸出算子

<<和>>輸入算子>>輸出算子<<北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page183.1.2.5處理子串(Substring)的函數(shù)簡(jiǎn)稱“子串函數(shù)”提取子串插入子串尋找子串刪除子串…北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page193.1.2.6字符串中的字符重載下標(biāo)算子[]char&operator[](intn);按字符定位下標(biāo)

intFind(charc,intstart);反向?qū)ふ?，定位尾部出現(xiàn)的字符

intFindLast(charc);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page203.2字符串的存儲(chǔ)結(jié)構(gòu)

和類定義3.2.1字符串的順序存儲(chǔ)3.2.2字符串類classString的存儲(chǔ)結(jié)構(gòu)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page213.2.1字符串的順序存儲(chǔ)對(duì)于串長(zhǎng)變化不大的字符串，可以有三種處理方案：（1）用S[0]作為記錄串長(zhǎng)的存儲(chǔ)單元。缺點(diǎn)：限制了串的最大長(zhǎng)度不能超過(guò)256。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page223.2.1字符串的順序存儲(chǔ)(續(xù))

（2）為存儲(chǔ)串的長(zhǎng)度，另辟一個(gè)存儲(chǔ)的地方。缺點(diǎn)：串的最大長(zhǎng)度一般是靜態(tài)給定的，不是動(dòng)態(tài)申請(qǐng)數(shù)組空間。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page233.2.1字符串的順序存儲(chǔ)(續(xù))

（3）用一個(gè)特殊的末尾標(biāo)記'\0'。例如：C++語(yǔ)言的string函數(shù)庫(kù)（＃include<string.h>）采用這一存儲(chǔ)結(jié)構(gòu)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page243.2.2字符串類classString的存儲(chǔ)結(jié)構(gòu)抽取子串函數(shù)例如：

Strings1="value-";s2=s1.Substr(2,3);

上述語(yǔ)句涉及的存儲(chǔ)形式如下頁(yè)所示。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page253.2.2字符串類classString的存儲(chǔ)結(jié)構(gòu)(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page263.2.2字符串類classString的存儲(chǔ)結(jié)構(gòu)(續(xù))微軟VC＋＋的CString類介紹自動(dòng)的動(dòng)態(tài)存儲(chǔ)管理，串的最大長(zhǎng)度不超過(guò)2GB容器型不必使用new和delete使用特點(diǎn)：變量申明CStrings6('x',6);//s6="xxxxxx"CStringcity="Philadelphia";//串常數(shù)作為初值賦值語(yǔ)句s1=s2="hithere";變量比較if(s1==s2)方法調(diào)用s1.MakeUpper();內(nèi)部字符比較if(s2[0]=='h')北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page273.3字符串運(yùn)算的算法實(shí)現(xiàn)1.串長(zhǎng)函數(shù)

intstrlen(char*s);2.串復(fù)制

char*strcpy(char*s1,char*s2);3．串拼接

char*strcat(char*s1,char*s2);4．串比較

intstrcmp(char*s1,char*s2);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page283.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)【算法3-1】字符串的復(fù)制char*strcpy(char*d,char*s){//這個(gè)程序的毛病是，如果字符串s比字符串d要長(zhǎng)，//這個(gè)程序沒(méi)有檢查拷貝出界，沒(méi)有報(bào)告錯(cuò)誤。//可能會(huì)造成d的越界

inti=0;while(s[i]!='\0'){d[i]=s[i];i++;}d[i]='\0';returnd;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page293.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-2】字符串的比較intstrcmp(char*d,char*s){inti=0;while(s[i]!='\0'&&d[i]!='\0'){if(d[i]>s[i])return1;elseif(d[i]<s[i])return-1;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page303.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))i++;}if(d[i]=='\0'&&s[i]!='\0')return-1;elseif(s[i]=='\0'&&d[i]!='\0')return1;return0;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page313.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-3】求字符串的長(zhǎng)度intstrlen(chard[]){inti=0;while(d[i]!=0)i++;returni;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page323.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-4】尋找字符char*strchr(char*d,charch){//按照數(shù)組指針d依次尋找字符ch，//如果找到ch，則將指針位置返回，//如果沒(méi)有找到ch，則為0值。i=0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page333.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))//循環(huán)跳過(guò)那些不是ch的字符while(d[i]!=0&&d[i]!=ch) i++;//當(dāng)本串不含字符ch，則在串尾結(jié)束；

//當(dāng)成功尋找到ch，返回該位置指針if(d[i]==0)return0;elsereturn&d[i];}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page343.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-5】反向?qū)ふ易址鹀har*strrchr(char*d,charch){//按照數(shù)組指針d，從其尾部反著尋找字符ch，

//如果找到ch，則將指針位置返回，

//如果沒(méi)有找到ch，則為0值。

i=0;//找串尾

while(d[i]!='\0') i++;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page353.3.1C++標(biāo)準(zhǔn)串運(yùn)算的實(shí)現(xiàn)(續(xù))//循環(huán)跳過(guò)那些不是ch的字符while(i>=0&&d[i]!=ch) ;//當(dāng)本串不含字符ch，則在串尾結(jié)束；

//當(dāng)成功尋找到ch，返回該位置指針if(i<0)return0;elsereturn&d[i];}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page363.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-7】創(chuàng)建算子(constructor)String::String(char*s){//先要確定新創(chuàng)字符串實(shí)際需要的存儲(chǔ)空間，s的類

//型為(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ū)域開(kāi)辟一塊空間，用于存

//儲(chǔ)初值s，把結(jié)束字符也包括進(jìn)來(lái)str＝newchar[size＋1];北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page373.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//開(kāi)辟空間不成功時(shí)，運(yùn)行異常，退出assert(str!='\0');//用標(biāo)準(zhǔn)字符串函數(shù)strcpy，將s完全

//復(fù)制到指針str所指的存儲(chǔ)空間strcpy(str,s);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page383.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-8】銷毀算子（destructor）String::~String(){//必須釋放動(dòng)態(tài)存儲(chǔ)空間delete[]str;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page393.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-9】拼接算子StringString::operator+(String&s){//把字符串s和本實(shí)例拼接成為一個(gè)長(zhǎng)串返回Stringtemp;//創(chuàng)建一個(gè)串tempintlen;//準(zhǔn)備工作，計(jì)算拼接后的長(zhǎng)串的長(zhǎng)度len=size+s.size;//把temp串創(chuàng)建時(shí)申請(qǐng)的存儲(chǔ)空間全部釋放delete[]temp.str;//準(zhǔn)備工作，開(kāi)辟空間，為存放長(zhǎng)串之用temp.str=newchar[len+1];北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page403.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//若開(kāi)辟動(dòng)態(tài)存儲(chǔ)空間不成功，則退出assert(temp.str!=0)；temp.size=len;//字符串str（以’\0’結(jié)尾）存到tempstrcpy(temp.str,str);//再把參數(shù)s的str和本實(shí)例的str拼接為長(zhǎng)串strcat(temp.str,s.str);returntemp;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page413.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-10】賦值算子StringString::operator=(String&s){//參數(shù)s將被賦值到本串//若本串的串長(zhǎng)和s的串長(zhǎng)不同，則應(yīng)該釋放本串的//str存儲(chǔ)空間，并開(kāi)辟新的空間if(size!=s.size){delete[]str;//釋放原存儲(chǔ)空間

str=newchar[s.size+1];北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page423.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//若開(kāi)辟動(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é)院，轉(zhuǎn)載或翻印必究Page433.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-11】抽取子串函數(shù)StringString::Substr(intindex,intcount){//取出一個(gè)子串返回，自下標(biāo)index開(kāi)始，長(zhǎng)度為countinti;//本串自下標(biāo)index開(kāi)始向右數(shù)直到串尾，長(zhǎng)度為leftintleft=size–index;Stringtemp;char*p,*q;//若下標(biāo)index值太大，超過(guò)本串實(shí)際串長(zhǎng)，則返回空串if(index>=size)//注意不是index>=size-1returntemp;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page443.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//若count超過(guò)自index以右的實(shí)際子串長(zhǎng)度，

//則把count變小if(count>left)count=left;//釋放原來(lái)的存儲(chǔ)空間delete[]temp.str;//張銘注釋：注意此語(yǔ)句！//若開(kāi)辟動(dòng)態(tài)存儲(chǔ)空間失敗，則退出temp.str=newchar[count+1];assert(temp.str!=0)；

//p的內(nèi)容是一個(gè)指針，

//指向目前暫無(wú)內(nèi)容的字符數(shù)組的首字符處p=temp.str;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page453.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//q的內(nèi)容是一個(gè)指針，

//指向本實(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;returntemp;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page463.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))【算法3-12】查找字符intString::Find(charc,intstart){//在本實(shí)例字符串尋找字符c，如果找到，則//將其下標(biāo)位置作為整數(shù)函數(shù)值返回，如果//c沒(méi)有找到，則為負(fù)值。參數(shù)start是下標(biāo)，//從start下標(biāo)開(kāi)始尋找c的工作,若start為//0，則從頭尋找inti=start;assert(i<size);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page473.3.2String串運(yùn)算的實(shí)現(xiàn)(續(xù))//循環(huán)跳過(guò)那些不是c的字符while(str[i]!=0&&str[i]!=c)i++;//當(dāng)本串不含字符c，則尋找到串尾結(jié)束，

//返回－1表示失??；當(dāng)成功尋找到c，返回它的

//下標(biāo)位置if(str[i]==0)//注意：不要搞成“==”return-1;elsereturni;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page483.4字符串的模式匹配模式匹配(patternmatching)一個(gè)目標(biāo)對(duì)象S（字符串）一個(gè)模板（pattern）P（字符串）任務(wù)：用給定的模板P，在目標(biāo)字符串S中搜索與模板P全同的一個(gè)子串，并求出S中第一個(gè)和P全同匹配的子串（簡(jiǎn)稱為“配串”），返回其首字符位置。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page49Ss0

s1

…

sisi+1

si+2

…

si+m-2

si+m-1

…

sn-1

‖‖‖‖‖P

p0

p1

p2…

pm-2pm-1為使模式P與目標(biāo)S匹配，必須滿足

p0

p1

p2…pm-1=si

si+1

si+2

…

si+m-1北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page50樸素模式匹配S=ababababababb…P=abababb

XabababbX

abababbX

abababbX

abababbXabababbX

abababb

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page51【算法3-13】模式匹配原始算法（其一）#include“String.h”//不是<String.h>#include<assert.h>intFindPat_1(StringS,StringP,intstartindex){//從S末尾倒數(shù)一個(gè)模板長(zhǎng)度位置

intLastIndex=S.strlen()-P.strlen();if(LastIndex<startindex)return(-1);//g為S的游標(biāo)，用模板P和S第g位置子串比較，

//若失敗則繼續(xù)循環(huán)

for(intg=startindex;g<=LastIndex;g++)if(P==S.Substr(g,P.strlen()))returng;//若for循環(huán)結(jié)束，則整個(gè)匹配失敗，返回值為負(fù)，

return(-1);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page523.4.1模式匹配原始算法(續(xù))【算法3-13】模式匹配原始算法（其二）intFindPat_2(StringS,StringP,intstartindex){//從S末尾倒數(shù)一個(gè)模板長(zhǎng)度位置

intLastIndex=S.strlen()-P.strlen();//開(kāi)始匹配位置startindex的值過(guò)大，匹配無(wú)法成功

if(LastIndex<startindex)return(-1);//i是指向S內(nèi)部字符的游標(biāo)，

//j是指向P內(nèi)部字符的游標(biāo)

inti=startindex,j=0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page533.4.1模式匹配原始算法(續(xù))//下面開(kāi)始循環(huán)匹配while(i<LastIndex&&

j<=P.strlen())if(P[j]==S[i]){i++;j++; }else{i=i-j+1;j=0; }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page543.4.1模式匹配原始算法(續(xù))//如果匹配成功，則返回該S子串的開(kāi)

//始位置；如果P和S匹配失敗，函數(shù)

//返回值為負(fù)

if(j>P.strlen())//“>”

可以嗎？

return(i-1);elsereturn-1;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page553.4.1樸素模式匹配(糾錯(cuò))【算法3-13】模式匹配原始算法（糾錯(cuò)）intFindPat_2(StringS,StringP,intstartindex){//從S末尾倒數(shù)一個(gè)模板長(zhǎng)度位置

intLastIndex=S.strlen()-P.strlen();//開(kāi)始匹配位置startindex的值過(guò)大，匹配無(wú)法成功

if(LastIndex<startindex)return(-1);//i是指向S內(nèi)部字符的游標(biāo)，

//j是指向P內(nèi)部字符的游標(biāo)

inti=startindex,j=0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page563.4.1樸素模式匹配糾錯(cuò)(續(xù))//下面開(kāi)始循環(huán)匹配while(i<S.strlen()&&

j<P.strlen())//“<=”呢？

if(P[j]==S[i]){i++;j++; }else{i=i-j+1;j=0; }錯(cuò)誤1：如果“i<LastIndex”，那么后面的就匹配不到。例如，abababababbabababb

S.strlen()=11，P.strlen()=7，LastIndex=4;“i=4，j=0”,匹配‘a(chǎn)’，接著，“i=5，j=1”就進(jìn)行不了。錯(cuò)誤2：

如果“j<=P.strlen()”，則P的結(jié)束符號(hào)‘\0’也拿來(lái)比較，除非正好匹配S的末端，否則出錯(cuò)！北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page573.4.1樸素模式匹配糾錯(cuò)(續(xù))//如果匹配成功，則返回該S子串的開(kāi)

//始位置；如果P和S匹配失敗，函數(shù)

//返回值為負(fù)

if(j>=P.strlen())//“>”

可以嗎？

return(i-j);elsereturn-1;}錯(cuò)誤3：

如果“j>P.strlen”，其實(shí)匹配結(jié)束時(shí)，正好j==P.size（因?yàn)槠ヅ渥詈笠粋€(gè)字符后，還j++）出錯(cuò)！其實(shí)“j==P.strlen”就可以！錯(cuò)誤4：

return(i-1);

匹配完成后，i指向S中最后一個(gè)字符的下一位，減去匹配串的長(zhǎng)度，才是開(kāi)始位。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page583.4.1模式匹配原始算法(續(xù))例如，aaaaaaaaaabaaaaaab分析假定目標(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í)間開(kāi)銷估計(jì)為O(m

n)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page59例1，aaaaaaaaaabaaaaaab

aaaaaab|aaaaaab例2，abcdefabcdeffabcdeff

abcdeff

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page60KMP算法思想Ss0

s1

…

si-j-1

si-j

si-j+1

si-j+2

…

si-2

si-1

si

…

sn-1

‖‖‖‖‖

P

p0

p1

p2…

pj-2

pj-1pj

則有

si-jsi-j+1

si-j+2

…

si-1

=p0

p1

p2…pj-1(1)

如果

p0

p1

…pj-2

p1

p2…pj-1 (2)

則立刻可以斷定

p0

p1

…pj-2

si-j+1

si-j+2

…

si-1(樸素匹配的)下一趟一定不匹配，可以跳過(guò)去北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page61同樣，若

p0

p1…pj-3

p2

p3…pj-1則再下一趟也不匹配，因?yàn)橛?/p>

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-k

si-k+1…si-1si

‖‖‖

pj-k

pj-k+1…pj-1pj‖‖‖

p0

p1…pk-1pk模式右滑j-k位北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page62模式右滑j-k位

si-jsi-j+1si-j+2

…si-ksi-k+1

…si-1si‖‖‖

‖‖‖‖

p0

p1

p2…

pj-k

pj-k+1…

pj-1pj‖‖‖

p0p1

…pk-1pk北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page633.4.2字符串的特征向量N設(shè)模板P由m個(gè)字符組成：記為P=q0q1q2q3……qm-1令特征向量N用于表示模板P的字符分布特征，并簡(jiǎn)稱N向量。它和P同長(zhǎng)，由m個(gè)特征數(shù)n0

…nm-1非負(fù)整數(shù)組成：記為N＝n0n1n2n3……nm-1

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page643.4.2字符串的特征向量N(續(xù))下面說(shuō)明ni的含義和它的遞歸定義：列出模板P開(kāi)頭的任意t個(gè)字符，把它稱為P的前綴子串。

q0q1q2…qt-1

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page653.4.2字符串的特征向量N(續(xù))

在P的第i位置的左邊，也取出t個(gè)字符，稱為i位置的左子串。

qi-t+1...qi-2qi-1qi北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page663.4.2字符串的特征向量N(續(xù))計(jì)算特征數(shù)ni設(shè)法求出最長(zhǎng)的（t最大的）能夠與前綴子串匹配的左子串（簡(jiǎn)稱第i位的最長(zhǎng)前綴串）。t就是要求的特征數(shù)ni。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page673.4.2字符串的特征向量N(續(xù))特征數(shù)ni(0≤ni≤i)是遞歸定義的，定義如下：①n0＝0，對(duì)于i>1的ni，假定已知前一位置的特征數(shù)ni-1，并且ni-1＝k；②如果qi

＝qk

，則ni

＝k＋1；③當(dāng)qi≠qk

且k≠0時(shí)，則令k＝nk-1;

讓③循環(huán)直到條件不滿足；④當(dāng)qi≠qk

且k＝0時(shí)，則ni＝0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page683.4.2字符串的特征向量N(續(xù))舉例：北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page693.4.2字符串的特征向量N(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page703.4.2字符串的特征向量N(續(xù))【算法3-14】計(jì)算向量Nint*Next(StringP){intm=P.strlen();//m為模板P的長(zhǎng)度

assert(m>0);//若m＝0，退出

int*N=newint[m];//動(dòng)態(tài)存儲(chǔ)區(qū)開(kāi)辟整數(shù)數(shù)組

assert(N!=0);//若開(kāi)辟存儲(chǔ)區(qū)域失敗，退出

N[0]=0;for(inti=1;i<m;i++)//分析P的每個(gè)位置i{intk=N[i-1];//第(i-1)位置的最長(zhǎng)前綴串長(zhǎng)度北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page713.4.2字符串的特征向量N(續(xù))//以下while語(yǔ)句遞推決定合適的前綴位置kwhile(k>0&&P[i]!=P[k]) k=N[k-1];//根據(jù)P[i]比較第k位置前綴字符，決定N[i]if(P[i]==P[k]) N[i]=k+1;else N[i]=0;}

returnN;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page723.4.3KMP模式匹配算法【算法3-15】KMP模式匹配算法intKMP_FindPat(StringS,StringP,int*N,intstartindex){//假定事先已經(jīng)計(jì)算出P的特征數(shù)組N，作為輸入?yún)?shù)

//S末尾再倒數(shù)一個(gè)模板長(zhǎng)度位置

intLastIndex=S.size-P.size;if((LastIndex-startindex)<0)return(-1);//startindex過(guò)大，匹配無(wú)法成功

inti;//i是指向S內(nèi)部字符的游標(biāo)，

intj=0;//j是指向P內(nèi)部字符的游標(biāo)，北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page733.4.3KMP模式匹配算法(續(xù))//S游標(biāo)i循環(huán)加1for(i=startindex;i<S.size;i++){//若當(dāng)前位置的字符不同，則用N循環(huán)求當(dāng)前的j，

//用于將P的恰當(dāng)位置與S的i位置對(duì)準(zhǔn)

while(P.str[j]!=S.str[i]&&j>0) j=N[j-1];//P[j]與S[i]相同，繼續(xù)下一步循環(huán)

if(P.str[j]==S.str[i])j++;//匹配成功，返回該S子串的開(kāi)始位置

if(j==P.size)return(i-j+1);};return(-1);//P和S整個(gè)匹配失敗，函數(shù)返回值為負(fù)}討論：如果“i<LastIndex”，那么后面的就匹配不到。例如，aaaaaaaaaabaaaaaab

S.size=11，P.size=7，LastIndex=4;“i=4，j=0”,匹配‘a(chǎn)’，接著，“i=5，j=1”就進(jìn)行不了。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page74KMP模式匹配示例（一）0123456P=abababbN=[0012340]0123456789101112S=ababababababb…abababb

Xi=6,j=6,N[j-1]=4abababb

Xi=8,

j=6,N[j-1]=4abababb

Xi=10,

j=6,j’=4abababb