數(shù)據(jù)結(jié)構(gòu)教程第4單元-串

1、數(shù)據(jù)結(jié)構(gòu)教程4 串授課老師：彭偉國計算機(jī)學(xué)院一、教學(xué)內(nèi)容：1、串的概念、類型定義2、串的存儲結(jié)構(gòu)3、串的模式匹配算法 二、教學(xué)要求：1、了解串的定義；理解串的存儲表示，掌握串的幾種實現(xiàn)方法。 2、掌握串的結(jié)構(gòu)特性以及串的基本操作，掌握針對字符串進(jìn)行操作的常用算法 , 熟練運用字符串處理函數(shù)。 3、掌握簡單的模式匹配算法。 第四章 串教學(xué)重點： 串的定義，串的表示和實現(xiàn)，定長順序存儲表示法，堆分配存儲表示法。 教學(xué)難點： 串的表示和實現(xiàn)，KMP模式匹配思想。第四章 串4.1 串的基本概念4.2 串的表示和實現(xiàn) 4.2.1 串的順序存儲結(jié)構(gòu)順序串 4.2.2 串的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈串4.3 串的模式匹

2、配第四章 串一、串和基本概念 串(String)是零個或多個字符組成的有限序列。一般記作S=“a1a2a3an”，其中S 是串名，雙引號括起來的字符序列是串值；ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(Empty String)，它不包含任何字符。 通常將僅由一個或多個空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如 和分別表示長度為1的空白串和長度為0的空串。4.1 串的基本概念 串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時的該子串的首字符對應(yīng)

3、的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設(shè)A和B分別為 A=“This is a string” B=“is” 則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號（或位置）為3。 特別地，空串是任意串的子串，任意串是其自身的子串。兩個串相等： 兩個串的長度相等， 并且各個對應(yīng)的字符也都相同。 例如: a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 則b、c是a的子串，位置分別是1和12，d不是a的子串 又如：a= “program” b= “Progr

4、am” c= “pro” d= “program ” 四個串彼此都不相等?！癶ello”和”hello”相等 串的基本運算如下: (1) StrAssign(&s,chars):將一個字符串常量賦給串s,即生成一個其值等于chars的串s。 (2) StrCopy(&s,t):串復(fù)制:將串t賦給串s。 (3) StrEqual(s,t):判串相等:若兩個串s與t相等則返回真；否則返回假。 (4) StrLength(s):求串長:返回串s中字符個數(shù)。二、串的抽象數(shù)據(jù)定義 (5) Concat(s,t):串連接:返回由兩個串s和t連接在一起形成的新串。 (6)SubStr(s,i,j):求子串:

5、返回串s中從第i(1iStrLength(s)個字符開始的、由連續(xù)j個字符組成的子串。 (7)InsStr(s1,i,s2):將串s2插入到串s1的第i(1iStrLength(s)+1)個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。 (8)DelStr(s,i,j):從串s中刪去從第i(1iStrLength(s)個字符開始的長度為j的子串,并返回產(chǎn)生的新串。 (9)RepStr(s,i,j,t):替換:在串s中,將第i(1iStrLength(s)個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。 (10) DispStr(s):串輸出:輸出串s的所有元素

6、值。1. ( 不包含任何字符（長度為0）的串 )稱為空串；( 由一個或多個空格（僅由空格符）組成的串 ) 稱為空白串。2. 設(shè)S=“A:/document/Mary.doc”，則strlen(s)= ( 20 ), “/”的字符定位的位置為( 3 )。3. 設(shè)串s1=ABCDEFG，s2=PQRST，則 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2) 的結(jié)果串是（ BCDEFEF ）。串運算舉例： 對于串的基本操作，許多高級語言均提供了相應(yīng)的運算或標(biāo)準(zhǔn)庫函數(shù)來實現(xiàn)。下面僅介紹幾種在C語言中常用的串運算。 1.字符數(shù)組: char ar110=h,e,

7、l,l,o,0;自己加上結(jié)束標(biāo)志 char ar210=“hello”;系統(tǒng)自動加上結(jié)束標(biāo)志0 2.字符指針: char *p=“hello”;系統(tǒng)自動加上結(jié)束標(biāo)志0 輸出字符指針就是輸出字符串,輸出字符指針的間接引用就是輸出單個字符分析下面程序段的運行結(jié)果: #include void main() char arr110=h,e,l,l,o,0 char arr210=hello; char *p=hello; coutarr1endl; coutarr2endl; coutarr13endl; coutarr24endl; coutpendl; cout*p+endl; cout*pen

8、dl; coutpendl; 運行結(jié)果:hellohellolohelloheello strcat(S,T) strlen(S) strcpy(S,T) strcmp(S,T） 對于字符串操作我們要求會靈活運用系統(tǒng)提供的標(biāo)準(zhǔn)函數(shù)來解決實際問題,使用時要引入庫 常用標(biāo)準(zhǔn)串函數(shù):4.2.1 串的順序存儲及其基本操作實現(xiàn) 串是一種特殊的線性表,在非緊縮格式中,它的每個結(jié)點僅由一個字符組成,因此存儲串的方法也就是存儲線性表的一般方法。存儲串最常用的方式是采用順序存儲,即把串的字符順序地存儲在內(nèi)存一片相鄰的空間,這稱為順序串。4.2 串的存儲結(jié)構(gòu) 順序存儲采用一般順序表的存儲結(jié)構(gòu),其類型定義如下: #

9、define MaxSize 100 typedef struct char dataMaxSize; int len; SqString; 其中,data域用來存儲字符串,len域用來存儲字符串的當(dāng)前長度,MaxSize常量表示允許所存儲字符串的最大長度。在C語言中每個字符串以0標(biāo)志結(jié)束。 順序串中實現(xiàn)串的基本運算如下: (1) StrAssign(str,cstr) 將一個字符串常量賦給串str,即生成一個其值等于cstr的串s。 void StrAssign(SqString &str,char cstr) int i; for (i=0;cstri!=0;i+) str.datai=c

10、stri; str.len=i; (2) StrCopy(s,t) 將串t復(fù)制給串s。void StrCopy(SqString &s,SqString t) /*引用型參數(shù)*/ int i; for (i=0;it.len;i+) s.datai=t.datai; s.len=t.len; (3) StrEqual(s,t) 判斷兩個串是否相等:若兩個串s與t相等返回真(1)；否則返回假(0)。 int StrEqual(SqString s,SqString t) int same=1,i; if (s.len!=t.len) same=0; /*長度不相等時返回0*/ else for

11、(i=0;is.len;i+) if (s.datai!=t.datai) /*有一個對應(yīng)字符不同時返回0*/ same=0; break; return same; (4) StrLength(s)求串長:返回串s中字符個數(shù)。int StrLength(SqString s) return s.len; (5) Concat(s,t) 返回由兩個串s和t連接在一起形成的新串。 SqString Concat(SqString s,SqString t) SqString str; int i; str.len=s.len+t.len; for (i=0;istr*/ str.datai=s.

12、datai; for (i=0;istr*/ str.datas.len+i=t.datai; return str; (6) SubStr(s,i,j) 返回串s中從第i(1iStrLength(s)個字符開始的、由連續(xù)j個字符組成的子串。 SqString SubStr(SqString s,int i,int j) SqString str;int k;str.len=0; if (is.len | js.len) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/ for (k=i-1;kstr*/ str.datak-i+1=s.datak; str

13、.len=j; return str; (7) InsStr(s1,i,s2) 將串s2插入到串s1的第i個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。 SqString InsStr(SqString s1,int i,SqString s2) int j;SqString str; str.len=0; if (is1.len+1) /*參數(shù)不正確時返回空串*/ printf(參數(shù)不正確n); return s1;for (j=0;jstr*/ str.dataj=s1.dataj;for(j=0;jstr*/ str.datai+j-1=s2.dataj;for

14、(j=i-1;jstr*/ str.datas2.len+j=s1.dataj; str.len=s1.len+s2.len; return str; (8) DelStr(s,i,j) 從串s中刪去第i(1iStrLength(s)個字符開始的長度為j的子串,并返回產(chǎn)生的新串。 SqString DelStr(SqString s,int i,int j) int k;SqString str; str.len=0; if (is.len | i+js.len+1) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/for (k=0;kstr*/ str.d

15、atak=s.datak;for(k=i+j-1;kstr*/ str.datak-j=s.datak; str.len=s.len-j; return str; (9) RepStr(s,i,j,t) 在串s中,將第i(1iStrLength(s)個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。 SqString RepStr(SqString s,int i,int j,SqString t) int k;SqString str; str.len=0; if (is.len | i+j-1s.len) /*參數(shù)不正確時返回空串*/ printf(參數(shù)不正確n); return

16、 str;for (k=0;kstr*/ str.datak=s.datak;for (k=0;kstr*/ str.datai+k-1=t.datak;for(k=i+j-1;kstr*/ str.datat.len+k-j=s.datak; str.len=s.len-j+t.len; return str; (10) DispStr(s)輸出串s的所有元素值。void DispStr(SqString s) int i; if (s.len0) for (i=0;is.len;i+) printf(%c,s.datai); printf(n); 例4.2 設(shè)計順序串上實現(xiàn)串比較運算Str

17、cmp(s,t)的算法。 解:本例的算法思路如下: (1)比較s和t兩個串共同長度范圍內(nèi)的對應(yīng)字符: 若s的字符t的字符,返回1； 若s的字符t的字符,返回-1； 若s的字符=t的字符,按上述規(guī)則繼續(xù)比較。 (2)當(dāng)(1)中對應(yīng)字符均相同時,比較s1和s2的長度: 兩者相等時,返回0； s的長度t的長度,返回1； s的長度t的長度,返回-1。 int Strcmp(SqString s,SqString t) int i,comlen; if (s.lent.len) comlen=s.len;/*求s和t的共同長度*/ else comlen=t.len; for (i=0;icomlen;

18、i+) /*逐個字符比較*/ if (s.datait.datai) return 1; if (s.len=t.len) /*s=t*/ return 0; else if (s.lent.len) /*st*/ 4.2.2 串的鏈?zhǔn)酱鎯捌浠静僮鲗崿F(xiàn) 也可以采用鏈?zhǔn)椒绞酱鎯Υ?即用單鏈表形式存儲串。這稱為鏈?zhǔn)酱蜴湸?鏈串中的結(jié)點類型定義: typedef struct snode char data; struct snode *next; LiString; 其中data域用來存儲組成字符串的字符,next域用來指向下一個結(jié)點。每個字符對應(yīng)一個結(jié)點,一個這樣的鏈表存儲一個字符串。下

19、圖所示是一個結(jié)點大小為1的鏈串。鏈串示意圖 下面討論在鏈串上實現(xiàn)串基本運算的算法。 (1) StrAssign(s,t) 將一個字符串常量t賦給串s,即生成一個其值等于t的串s。以下采用尾插法建立鏈串。 void StrAssign(LiString *&s,char t) int i; LiString *r,*p;/*r始終指向尾結(jié)點*/ s=(LiString *)malloc(sizeof(LiString); r=s; for (i=0;ti!=0;i+) p=(LiString *)malloc(sizeof(LiString); p-data=ti;r-next=p;r=p;r-

20、next=NULL; (2) StrCopy(s,t) 將串t復(fù)制給串s。以下采用尾插法建立復(fù)制后的鏈串s。 void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(sizeof(LiString);r=s;/*r始終指向尾結(jié)點*/ while (p!=NULL) /*將t的所有結(jié)點復(fù)制到s*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;r-next=q;r=q; p=p-next; r-next=NULL; (3)

21、 StrEqual(s,t) 判斷兩個串是否相等:若兩個串s與t相等則返回真(1)；否則返回假(0)。 int StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; while (p!=NULL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL) return 1; else return 0; (4) StrLength(s)求串長:返回串s中字符個數(shù)。 int StrLength(LiString *s) int i=0; LiStri

22、ng *p=s-next; while (p!=NULL) i+; p=p-next; return i; (5) Concat(s,t) 返回由兩個串s和t連接在一起形成的新串。 LiString *Concat(LiString *s,LiString *t) LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str; while (p!=NULL) /*將s的所有結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;

23、r-next=q;r=q; p=p-next; p=t-next; while (p!=NULL) /*將t的所有結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str; (6) SubStr(s,i,j) 返回串s中從第i(1iStrLength(s)個字符開始的、由連續(xù)j個字符組成的子串。 LiString *SubStr(LiString *s,int i,int j) int k; LiString *str,*p=s

24、-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str;if (iStrLength(s) | jStrLength(s) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/ for (k=0;knext; for (k=1;kstr*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; r-next=NULL; return str; (7) InsStr(s1,i,

25、s2) 將串s2插入到串s1的第i(1iStrLength(s)+1)個字符中,即將s2的第一個字符作為s1的第i個字符,并返回產(chǎn)生的新串。 LiString *InsStr(LiString *s,int i,LiString *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str; if (iStrLength(s)+1) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/ for (k=1;kdata=p-dat

26、a;q-next=NULL; r-next=q;r=q;p=p-next; while (p1!=NULL) /*將t的所有結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p1-data;q-next=NULL; r-next=q;r=q; p1=p1-next; while (p!=NULL) /*將*p及其后的結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; r-next=N

27、ULL;return str; (8) DelStr(s,i,j) 從串s中刪去從第i(1iStrLength(s)個字符開始的長度為j的子串,并返回產(chǎn)生的新串。 LiString *DelStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str;if (iStrLength(s) | jStrLength(s) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/for (k=0;kdata=

28、p-data;q-next=NULL; r-next=q;r=q;p=p-next; for (k=0;knext;while (p!=NULL) /*將*p及其后的結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; r-next=NULL; return str; (9) RepStr(s,i,j,t) 在串s中,將第i(1iStrLength(s)個字符開始的j個字符構(gòu)成的子串用串t替換,并返回產(chǎn)生的新串。 LiString *RepStr(L

29、iString *s,int i,int j,LiString *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); r=str; if (iStrLength(s)|jStrLength(s) printf(參數(shù)不正確n); return str; /*參數(shù)不正確時返回空串*/ for (k=0;kdata=p-data;q-next=NULL; r-next=q;r=q;p=p-next; for (k=0;knext; while (p1!=NULL) /

30、*將t的所有結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p1-data;q-next=NULL; r-next=q;r=q;p1=p1-next; while (p!=NULL) /*將*p及其后的結(jié)點復(fù)制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; r-next=NULL;return str; (10) DispStr(s) 輸出串s的所有元素值。 void DispStr(

31、LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data); p=p-next;printf(n); 例4.3 在鏈串中,設(shè)計一個算法把最先出現(xiàn)的子串a(chǎn)b改為xyz。 解:在串s中找到最先出現(xiàn)的子串a(chǎn)b,p指向data域值為a的結(jié)點,其后為data域值為b的結(jié)點。將它們的data域值分別改為x和z,再創(chuàng)建一個data域值為y的結(jié)點,將其插入到*p之后。本例算法如下: void Repl(LiString *&s) LiString *p=s-next,*q;int find=0; while (p-next!=NULL

32、& find=0) if(p-data=a&p-next-data=b)/*找到*/ p-data=x;p-next-data=z; /*替換為xyz*/ q=(lstring *)malloc(sizeof(lstring); q-data=y;q-next=p-next;p-next=q; find=1; else p=p-next; 設(shè)有主串s和子串t,子串t的定位就是要在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標(biāo)串,把子串t稱為模式串,因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個模式串t；不成功則指目標(biāo)串s中不存在模式串t。 4.3 串的模式匹配 模式匹配

33、的應(yīng)用在非常廣泛。例如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。 模式匹配是一個較為復(fù)雜的串操作過程。迄今為止，人們對串的模式匹配提出了許多思想和效率各不相同的計算機(jī)算法。介紹兩種主要的模式匹配算法。4.3.1 Brute-Force算法 Brute-Force簡稱為BF算法,亦稱簡單匹配算法,其基本思路是: 從目標(biāo)串s=s0s1sn-1的第一個字符開始和模式串t=t0t1tm-1中的第一個字符比較,若相等,則繼續(xù)逐個比較后續(xù)字符；否則從目標(biāo)串s的第二個字符開始重新與模式串t的第一個字符進(jìn)行比較。依次類推,若從

34、模式串s的第i個字符開始,每個字符依次和目標(biāo)串t中的對應(yīng)字符相等,則匹配成功,該算法返回i；否則,匹配失敗,函數(shù)返回-1。 例如,設(shè)目標(biāo)串s=“cddcdc”,模式串t=“cdc”。s的長度為n(n=6),t的長度為m(m=3)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。BF模式匹配過程如下所示。int index(SqString s,SqString t) int i=0,j=0,k; while (is.length & j=t.length) k=i-t.length; /返回匹配的第一個字符的下標(biāo) else k=-1; /模式匹配不成功 retu

35、rn k; 這個算法簡單,易于理解,但效率不高,主要原因是:主串指針i在若干個字符序列比較相等后,若有一個字符比較不相等,仍需回溯(即i=i-j+1)。該算法在最好情況下的時間復(fù)雜度為O(m),即主串的前m個字符正好等于模式串的m個字符。在最壞情況下的時間復(fù)雜度為O(n*m)。 理解該算法的關(guān)鍵點是： 當(dāng)?shù)谝淮蝧itj時：主串要退回（即回溯）到i-j+1的位置，而模式串也要退回到第一個字符（即j=0的位置）。但是，我們知道當(dāng)比較出現(xiàn)sitj時：應(yīng)該有si-1=tj-1，si-j+1=t1， si-j=t0 ,即已經(jīng)出現(xiàn)有“部分匹配”的結(jié)果。我們能不能利用這些部分匹配信息，消除主串的回溯以提高算

36、法的效率呢？ KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,簡稱KMP算法。該算法較BF算法有較大改進(jìn),主要是消除了主串指針的回溯,從而使算法效率有了某種程度的提高。 4.3.2 KMP算法 每當(dāng)一趟匹配過程出現(xiàn)字符不相等時，主串指示器不用回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式串的指示器向右“滑動”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。 所謂真子串是指模式串t存在某個k(0kj)，使得t0t1tk = tj-ktj-k+1tj 成立。 例如，t= abab, 即t0t1t2t3 也就是說， “ab”是真子串。 真子串就是模式串中隱藏的信息，利用它來

37、提高模式匹配的效率。 一般情況:設(shè)主串s=s0s1sn-1,模式t=t0t1tm-1,在進(jìn)行第i趟匹配時，出現(xiàn)以下情況：這時，應(yīng)有t0t1tj-1=si-jsi-j+1si-1 (4.1)如果在模式t中，t0t1tj-1t1t2tj(4.2) 則回溯到si-j+1開始與t匹配，必然“失配”，理由很簡單：由(4.1)式和(4.2)式綜合可知：t0t1tj-1si-j+1si-j+2si 既然如此，回溯到si-j+1開始與t匹配可以不做。那么，回溯到si-j+2開始與t匹配又怎么樣？從上面推理可知，如果: t0t1tj-2t2t3tj仍然有 t0t1tj-2si-j+2si-j+3si 這樣的比較

38、仍然“失配”。依此類推，直到對于某一個值k，使得： t0t1tk-2 tj-k+1tj-k+2tj-1 且 t0t1tk-1=tj-ktj-k+1tj-1“才有 tj-ktj-k+1tj-1=si-ksi-k+1si-1=t0t1tk-1 說明下一次可直接比較si和tk，這樣，我們可以直接把第i趟比較“失配”時的模式t從當(dāng)前位置直接右滑j-k位。而這里的k即為nextj。 例如t=“abab”,由于“t0t1” =“t2t3”(這里k=1,j=3），設(shè)s=abacabab,t=abab,第一次匹配過程如下所示。 此時不必從i=1(i=i-j+1=1), j=0重新開始第二次匹配。因t0t1,

39、s1=t1, 必有s1t0, 又因t0 =t2, s2=t2, 所以必有s2=t0。因此,第二次匹配可直接從i=3, j=1開始。 為此,定義nextj函數(shù)如下: maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng)此集合非空時 -1 當(dāng)j=0時 0 其他情況nextj=j0123tjababnextj-1001t=“abab”對應(yīng)的next數(shù)組如下:void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.length-1) if (k=-1 | t.dataj=t.datak)

40、/k為-1或比較的字符相等時 j+;k+; nextj=k; else k=nextk; 由模式串t求出next值的算法int KMPIndex(SqString s,SqString t) int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (is.length & j=t.length) v=i-t.length; else v=-1; /返回不匹配標(biāo)志 return v; KMP算法 設(shè)主串s的長度為n,子串t長度為m。 在KMP算法中求next數(shù)組的時間復(fù)雜度為O(m),在后面的匹配中因主串s的下標(biāo)不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時間復(fù)雜度為O(n+m)。 例如,設(shè)目標(biāo)串s=“aaabaaaab”,模式串t=“aaaab”。s的長度為n(n=9),t的長度為m(m=5)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。KMP模式匹配過程如下所示。j01234tjaaaabnextj-10123 上述定義的next在某些情況下尚有缺陷。 例如,模式“aaaab”在和主串“aaabaaaab”匹配時,當(dāng)i=3,j=3時