數(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字符串的存儲結(jié)構(gòu)和類定義3.3字符串運算的算法實現(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個或多個字符的順序排列所組成的復(fù)合數(shù)據(jù)結(jié)構(gòu)，簡稱“串”。串的長度：一個字符串所包含的字符個數(shù)?？沾洪L度為零的串，它不包含任何字符內(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碼對128個符號（字符集charset）進行編碼北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page73.1.1.3字符的編碼順序為了字符串間比較和運算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。其實大多數(shù)情況下就是字典序中文字符串有些特例，例如“筆劃”序北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page83.1.1.4C++標(biāo)準string標(biāo)準字符串：將C++的<string.h>函數(shù)庫作為字符串?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)準string(續(xù))1.串長函數(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)準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)準string(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page123.1.2String抽象數(shù)據(jù)類型字符串類（classString）：不采用charS[M]的形式而采用一種動態(tài)變長的存儲結(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ù)簡稱“子串函數(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字符串的存儲結(jié)構(gòu)

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

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

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

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

上述語句涉及的存儲形式如下頁所示。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page253.2.2字符串類classString的存儲結(jié)構(gòu)(續(xù))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page263.2.2字符串類classString的存儲結(jié)構(gòu)(續(xù))微軟VC＋＋的CString類介紹自動的動態(tài)存儲管理，串的最大長度不超過2GB容器型不必使用new和delete使用特點：變量申明CStrings6('x',6);//s6="xxxxxx"CStringcity="Philadelphia";//串常數(shù)作為初值賦值語句s1=s2="hithere";變量比較if(s1==s2)方法調(diào)用s1.MakeUpper();內(nèi)部字符比較if(s2[0]=='h')北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page273.3字符串運算的算法實現(xiàn)1.串長函數(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)準串運算的實現(xiàn)【算法3-1】字符串的復(fù)制char*strcpy(char*d,char*s){//這個程序的毛病是，如果字符串s比字符串d要長，//這個程序沒有檢查拷貝出界，沒有報告錯誤。//可能會造成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)準串運算的實現(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)準串運算的實現(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)準串運算的實現(xiàn)(續(xù))【算法3-3】求字符串的長度intstrlen(chard[]){inti=0;while(d[i]!=0)i++;returni;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page323.3.1C++標(biāo)準串運算的實現(xiàn)(續(xù))【算法3-4】尋找字符char*strchr(char*d,charch){//按照數(shù)組指針d依次尋找字符ch，//如果找到ch，則將指針位置返回，//如果沒有找到ch，則為0值。i=0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page333.3.1C++標(biāo)準串運算的實現(xiàn)(續(xù))//循環(huán)跳過那些不是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)準串運算的實現(xiàn)(續(xù))【算法3-5】反向?qū)ふ易址鹀har*strrchr(char*d,charch){//按照數(shù)組指針d，從其尾部反著尋找字符ch，

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

//如果沒有找到ch，則為0值。

i=0;//找串尾

while(d[i]!='\0') i++;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page353.3.1C++標(biāo)準串運算的實現(xiàn)(續(xù))//循環(huán)跳過那些不是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串運算的實現(xiàn)(續(xù))【算法3-7】創(chuàng)建算子(constructor)String::String(char*s){//先要確定新創(chuàng)字符串實際需要的存儲空間，s的類

//型為(char*)，作為新創(chuàng)字符串的初值。確定

//s的長度，用標(biāo)準字符串函數(shù)strlen(s)計算長度size=strlen(s);

//然后，在動態(tài)存儲區(qū)域開辟一塊空間，用于存

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

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

str=newchar[s.size+1];北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page423.3.2String串運算的實現(xiàn)(續(xù))//若開辟動態(tài)存儲空間失敗，則退出正常運行

assert(str!=0)；

size=s.size;}strcpy(str,s.str);//返回本實例，作為String類的一個實例return*this;}

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

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

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

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

//指向本實例串的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串運算的實現(xiàn)(續(xù))【算法3-12】查找字符intString::Find(charc,intstart){//在本實例字符串尋找字符c，如果找到，則//將其下標(biāo)位置作為整數(shù)函數(shù)值返回，如果//c沒有找到，則為負值。參數(shù)start是下標(biāo)，//從start下標(biāo)開始尋找c的工作,若start為//0，則從頭尋找inti=start;assert(i<size);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page473.3.2String串運算的實現(xiàn)(續(xù))//循環(huán)跳過那些不是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)一個目標(biāo)對象S（字符串）一個模板（pattern）P（字符串）任務(wù)：用給定的模板P，在目標(biāo)字符串S中搜索與模板P全同的一個子串，并求出S中第一個和P全同匹配的子串（簡稱為“配串”），返回其首字符位置。北京大學(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ù)一個模板長度位置

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é)束，則整個匹配失敗，返回值為負，

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

intLastIndex=S.strlen()-P.strlen();//開始匹配位置startindex的值過大，匹配無法成功

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ù))//下面開始循環(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子串的開

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

//返回值為負

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

可以嗎？

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

intLastIndex=S.strlen()-P.strlen();//開始匹配位置startindex的值過大，匹配無法成功

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樸素模式匹配糾錯(續(xù))//下面開始循環(huán)匹配while(i<S.strlen()&&

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

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

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

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

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

//返回值為負

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

可以嗎？

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

如果“j>P.strlen”，其實匹配結(jié)束時，正好j==P.size（因為匹配最后一個字符后，還j++）出錯！其實“j==P.strlen”就可以！錯誤4：

return(i-1);

匹配完成后，i指向S中最后一個字符的下一位，減去匹配串的長度，才是開始位。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page583.4.1模式匹配原始算法(續(xù))例如，aaaaaaaaaabaaaaaab分析假定目標(biāo)S的長度為n，模板P長度為m，m≤n在最壞的情況下，每一次循環(huán)都不成功，則一共要進行比較（n-m+1）次每一次“相同匹配”比較所耗費的時間，是P和S逐個字符比較的時間，最壞情況下，共m次。因此，整個算法的最壞時間開銷估計為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(樸素匹配的)下一趟一定不匹配，可以跳過去北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page61同樣，若

p0

p1…pj-3

p2

p3…pj-1則再下一趟也不匹配，因為有

p0

p1…pj-3

si-j+2

si-j+3…si-1直到對于某一個“k”值(首尾串長度)，使得

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個字符組成：記為P=q0q1q2q3……qm-1令特征向量N用于表示模板P的字符分布特征，并簡稱N向量。它和P同長，由m個特征數(shù)n0

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

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

q0q1q2…qt-1

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

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

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

＝qk

，則ni

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

且k≠0時，則令k＝nk-1;

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

且k＝0時，則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】計算向量Nint*Next(StringP){intm=P.strlen();//m為模板P的長度

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

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

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

N[0]=0;for(inti=1;i<m;i++)//分析P的每個位置i{intk=N[i-1];//第(i-1)位置的最長前綴串長度北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page713.4.2字符串的特征向量N(續(xù))//以下while語句遞推決定合適的前綴位置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)計算出P的特征數(shù)組N，作為輸入?yún)?shù)

//S末尾再倒數(shù)一個模板長度位置

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

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位置對準

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子串的開始位置

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

S.size=11，P.size=7，LastIndex=4;“i=4，j=0”,匹配‘a(chǎn)’，接著，“i=5，j=1”就進行不了。北京大學(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