第4章串簽到掃碼下載文旌課堂APP掃碼簽到（202X.X.XXXX:00至202X.X.XXXX:10）簽到方式教師通過“文旌課堂APP”生成簽到二維碼，并設(shè)置簽到時間，學(xué)生通過“文旌課堂APP”掃描“簽到二維碼”進(jìn)行簽到。。串本章導(dǎo)讀串是字符串的簡稱，它的每個數(shù)據(jù)元素都是字符。串作為一種特殊的線性表，具有廣泛的應(yīng)用，如文本編輯、信息檢索等。本章首先介紹串的定義及基本操作，然后介紹串的順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)，最后介紹串的模式匹配算法。

第4章串知識目標(biāo)

第4章 理解串的定義。 掌握串的基本操作。 掌握串的順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)。 掌握串的模式匹配算法，包括BF算法和KMP算法。串技能目標(biāo)

第4章 能使用串解決實(shí)際問題。 能使用串的模式匹配算法定位串。串素質(zhì)目標(biāo)

第4章 加強(qiáng)實(shí)踐練習(xí)，自覺提升專業(yè)技能和職業(yè)素養(yǎng)。 通過對算法的改進(jìn)，培養(yǎng)科學(xué)嚴(yán)謹(jǐn)、精益求精的工匠精神。Content第4章串的存儲結(jié)構(gòu)串概述串的模式匹配算法4.1串概述第4章串4.1串概述串是由若干字符組成的有限序列，通常記作str='a0a1a2…an-1'或str="a0a1a2…an-1"。其中，str是串名；用單引號或雙引號括起來的字符序列是串值，它可以是字母、數(shù)字或其他字符；n（n≥0）是串中字符的個數(shù)，也稱為串的長度，當(dāng)n=0時稱為空串。例如，串s='Python'，其中s是串名，Python是串值，串的長度是6。通常將僅由一個或多個空格組成的串稱為空白串?？沾涂瞻状遣煌?。例如，''（不含任何字符）表示長度為0的空串；''（含一個空格）表示長度為1的空白串。4.1.1串的定義4.1串概述提示如果單引號本身是串中的一個字符，那么串可以用雙引號括起來；反之，如果雙引號本身是串中的一個字符，那么串可以用單引號括起來。例如：a="I'mOK!"b='Itoldmyfriend,"Pythonismyfavoritelanguage!"'如果串中既包含單引號又包含雙引號，那么可以用轉(zhuǎn)義字符“\”來標(biāo)識。例如：c='I\'m\"OK\"!'以上串的內(nèi)容是“I'm"OK"!”。4.1串概述串中任意連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串稱為主串。子串在主串中第一次出現(xiàn)時第一個字符的位置（即該字符在串中的序號，串中首字符的序號為0，以此類推）稱為該子串在主串中的下標(biāo)或索引。當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時，稱兩個串是相等的。例如，s='abcdefgh'，s1='abc'，s2='def'，s3='abc'，則s1、s2和s3都稱為s的子串，且稱s為主串。s1和s3在s中的下標(biāo)均為0，s2在s中的下標(biāo)為3，s1和s3是相等的。串的基本操作與線性表類似，其定義如表4-1所示。4.1.2串的基本操作4.1串概述基本操作說明__init__()初始化串，即構(gòu)造一個串empty()判斷串是否為空，若為空串，則返回True，否則返回Falselength()求串的長度，即串中數(shù)據(jù)元素的個數(shù)clear()串清空，即將串設(shè)置為空串subString(begin,len)求子串，返回串的第begin（0≤begin＜length()）個字符起長度為len（0＜

len≤length()-begin）的子串insert(s,pos,t)串插入。已知串s和串t，在串s的第pos（0≤pos≤length()）個位置之前插入串tdelete(pos,n)串刪除。已知串s，在串s中刪除第pos（0≤pos≤length()-1）個位置起長度為n（0＜n≤length()-pos）的子串index(s,t,pos)串定位。已知串s和串t（非空），若串s中存在和串t相同的子串，則返回串t在串s中第pos（0≤pos＜length()）個字符起第一次出現(xiàn)的位置，否則返回-1compare(s,t)串比較。已知串s和串t，若s＞t，則返回1；若s=t，則返回0；若s＜t，則返回-1copy(t,s)串復(fù)制。已知串s和串t，將串s的內(nèi)容復(fù)制到串t中concat(t,s,p)串連接。已知串s和串p，用t返回由s和p連接而成的新串表4-1串基本操作的定義4.2串的存儲結(jié)構(gòu)第4章串4.2串的存儲結(jié)構(gòu)串的順序存儲是指用一組地址連續(xù)的存儲單元依次存放串的字符序列。在這種存儲結(jié)構(gòu)中，按照預(yù)定義的大小為每個串分配一個固定長度的存儲區(qū)，且這個存儲區(qū)在程序運(yùn)行期間不再改變，故串的順序存儲也稱為串的靜態(tài)存儲。采用順序存儲結(jié)構(gòu)的串稱為順序串。例如，串s=‘Python’的順序存儲結(jié)構(gòu)如下圖所示。4.2.1串的順序存儲——順序串4.2串的存儲結(jié)構(gòu)classSqString: #定義順序串類

def__init__(self,obj): #初始化串

ifobjisNone: #構(gòu)造空串

self.data=[] #串中的數(shù)據(jù)元素

self.length=0 #串長

elifisinstance(obj,str): #以字符串構(gòu)造串

self.length=len(obj) self.data=[None]*self.length 順序串的構(gòu)造方法如下。4.2串的存儲結(jié)構(gòu)

foriinrange(self.length): #遍歷串

self.data[i]=obj[i] #為串賦值

elifisinstance(obj,list): #以列表構(gòu)造串

self.length=len(obj)self.data=[None]*self.lengthforiinrange(self.length): #遍歷列表

self.data[i]=obj[i] #為串賦值順序串的基本操作包括串插入、串刪除、串定位和求子串等，其中最常用的操作是串定位（將在4.3節(jié)詳細(xì)介紹）和求子串。4.2串的存儲結(jié)構(gòu)求子串是指返回串中從指定下標(biāo)begin開始，長度為len的子串序列，其具體步驟如下。（1）判斷參數(shù)begin和len是否滿足條件0≤begin＜串長和0＜len≤串長-begin。（2）若滿足條件，則返回子串序列。defsubString(self,begin,len): #求子串

ifbegin<0orbegin>=self.lengthorlen<=0orlen>self.length-begin:raiseException('參數(shù)不滿足條件')tmp=[None]*len #初始化子串

foriinrange(begin,begin+len):tmp[i-begin]=self.data[i] #復(fù)制子串

returnSqString(tmp).data #返回子串【算法描述】4.2串的存儲結(jié)構(gòu)串的鏈?zhǔn)酱鎯κ侵赣脝捂湵泶鎯Υ?。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的串稱為鏈串。當(dāng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，鏈串中每個結(jié)點(diǎn)的數(shù)據(jù)域既可以存放一個字符，也可以存放多個字符（稱為塊）。通常將結(jié)點(diǎn)數(shù)據(jù)域中存放字符的個數(shù)稱為結(jié)點(diǎn)大小。例如，對于串str=‘DATASTRUCTURE’，結(jié)點(diǎn)大小為1和結(jié)點(diǎn)大小為5的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別如下圖所示。4.2.2串的鏈?zhǔn)酱鎯Α湸?.2串的存儲結(jié)構(gòu)由上圖可以看出，當(dāng)結(jié)點(diǎn)大小大于1時，由于串長不一定是結(jié)點(diǎn)大小的整數(shù)倍，也就是說鏈表的尾結(jié)點(diǎn)不一定總能被字符占滿，此時就須在未占滿的數(shù)據(jù)域中填充特殊符號“#”或其他非串值字符。在設(shè)計(jì)鏈串時，結(jié)點(diǎn)大小直接影響串處理的效率。結(jié)點(diǎn)大小越小，存儲密度越小，串的相關(guān)操作越方便，但存儲量占用較大。相反，結(jié)點(diǎn)大小越大，存儲密度越大，串的相關(guān)操作（如插入、刪除等）越復(fù)雜，但存儲量占用較小。在實(shí)際應(yīng)用中為便于操作，通常將鏈串的結(jié)點(diǎn)大小設(shè)置為1。4.2串的存儲結(jié)構(gòu)提示當(dāng)結(jié)點(diǎn)大小為1時，鏈串中基本操作的實(shí)現(xiàn)與單鏈表類似，此處不再贅述?？傮w而言，相較于順序串，鏈串不夠靈活，存儲量占用大且操作復(fù)雜，但對于串的某些基本操作（如連接）來說較方便。在實(shí)際應(yīng)用中，用戶可根據(jù)具體情況選擇合適的存儲結(jié)構(gòu)。4.3串的模式匹配算法第4章串4.3串的模式匹配算法4.3.1BF算法BF（brute-force）算法是最簡單且直觀的模式匹配算法，其基本思想是從目標(biāo)串的指定字符起和模式串的首字符進(jìn)行比較，若相等，則繼續(xù)逐個比較下一個字符，否則從目標(biāo)串的下一個字符起重新和模式串的首字符進(jìn)行比較。以此類推，直到模式串的每個字符依次和目標(biāo)串的一個連續(xù)的字符序列相等，則匹配成功，并返回和模式串的第一個字符相等的字符在目標(biāo)串中的位置，否則返回-1。為便于理解，下面用一個具體的實(shí)例說明BF算法的模式匹配過程。例如，目標(biāo)串s='acabaabaabcacbc'，模式串t='abaabc'，分別使用變量i和j（初始均為0）遍歷s和t，使用BF算法判斷模式串t與目標(biāo)串s是否匹配的過程如下。4.3串的模式匹配算法（1）第1趟從i=0、j=0開始依次匹配。當(dāng)i=1、j=1時，匹配失敗。此時，須將i從i=1開始，將j回溯到j(luò)=0重新進(jìn)行匹配。（2）第2趟從i=1、j=0開始依次匹配，可以發(fā)現(xiàn)匹配失敗。此時，須將i從i=2開始，將j回溯到j(luò)=0重新進(jìn)行匹配。（3）第3趟從i=2、j=0開始依次匹配。當(dāng)i=7、j=5時，匹配失敗。此時，須將i從i=3開始，將j回溯到j(luò)=0重新進(jìn)行匹配。4.3串的模式匹配算法（4）第4趟從i=3、j=0開始依次匹配，可以發(fā)現(xiàn)匹配失敗。此時，須將i從i=4開始，將j回溯到j(luò)=0重新進(jìn)行匹配。（5）第5趟從i=4、j=0開始依次匹配。當(dāng)i=5、j=1時，匹配失敗。此時，須將i從i=5開始，將j回溯到j(luò)=0重新進(jìn)行匹配。（6）第6趟從i=5、j=0開始依次匹配。當(dāng)i=10、j=5時，模式串t的每個字符依次和目標(biāo)串s的一個連續(xù)的字符序列相等，此時匹配成功。4.3串的模式匹配算法defbf(str1,str2,pos): #利用BF算法進(jìn)行串的模式匹配

i=pos #i為目標(biāo)串str1的指定開始匹配位置

j=0 #j為模式串str2的起始位置

whilei<len(str1)andj<len(str2):ifstr1[i]==str2[j]: #目標(biāo)串與模式串的字符相等

i+=1 #目標(biāo)串的遍歷變量后移

j+=1 #模式串的遍歷變量后移

else: #變量回溯

i=i-j+1 #目標(biāo)串的下一個位置

j=0 #模式串的起始位置【算法描述】4.3串的模式匹配算法'''如果在目標(biāo)串中找到模式串，則返回模式串的首字符在目標(biāo)串中的位置'''ifj==len(str2):returni-len(str2)else:return-1 #未匹配成功，返回-1【算法分析】使用BF算法進(jìn)行模式匹配時，時間主要花費(fèi)在字符的比較上。假設(shè)目標(biāo)串的長度為n，模式串的長度為m，則BF算法在最好情況下，即第一次就匹配成功，此時比較次數(shù)為模式串的長度m，即算法的最好時間復(fù)雜度為O(m)；BF算法在最壞情況下，即每次匹配至模式串的最后一個字符時失敗，且比較了目標(biāo)串中所有長度為m的子串，此時比較次數(shù)為n×(n-m+1)，即算法的最壞時間復(fù)雜度為O(n×m)。4.3串的模式匹配算法4.3.2KMP算法KMP（Knuth-Morris-Pratt）算法是在BF算法的基礎(chǔ)上改進(jìn)而來的，其目的是消除某次匹配失敗時目標(biāo)串開始比較位置的回溯，從而提高匹配效率。KMP算法的基本思想是每當(dāng)一趟匹配過程中出現(xiàn)字符不相等時，指向目標(biāo)串的指針無須回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式串向右移動一段距離后繼續(xù)比較。因此，KMP算法要解決的關(guān)鍵問題是，當(dāng)某次匹配不成功時，如何確定模式串向右移動的距離。也就是說，當(dāng)目標(biāo)串的第i個字符與模式串的第j個字符不相等時，目標(biāo)串的第i個字符應(yīng)該重新與模式串的哪個字符繼續(xù)比較。這時，可借助前綴數(shù)組next，其定義如下。4.3串的模式匹配算法其中，“t0t1…tk-1”為模式串的前綴，“tj-ktj-k+1…tj-1”為模式串的后綴，k為前綴和后綴最長共有元素的長度，也就是當(dāng)目標(biāo)串的第i個字符與模式串的第j個字符不相等時，模式串中下一次與目標(biāo)串的第i個字符進(jìn)行比較的字符的位置。4.3串的模式匹配算法提示前綴是除了最后一個字符外，一個串的全部頭部集合。后綴是除了第一個字符外，一個串的全部尾部集合。需要注意的是，從中間位置截取的串不屬于前綴或后綴。例如，串'good'的前綴為{'g','go','goo'}，后綴為{'d,'od','ood'}。4.3串的模式匹配算法借助前綴數(shù)組next，KMP算法的具體步驟如下。（1）從目標(biāo)串的第pos個字符開始，與模式串的字符逐個進(jìn)行匹配，變量i和j分別指向目標(biāo)串和模式串中當(dāng)前進(jìn)行匹配的字符。（2）當(dāng)目標(biāo)串的第i個字符與模式串的第j個字符相等時，變量i和j同時加1，繼續(xù)匹配下一個字符；當(dāng)目標(biāo)串的第i個字符與模式串的第j個字符不相等時，變量i不變，模式串向右移動，直到變量j回溯到next[j]所指示的位置，并與目標(biāo)串的第i個字符重新進(jìn)行匹配；當(dāng)變量j=-1時，變量i和j須同時加1，即從目標(biāo)串的第i+1個、模式串的第j+1個字符起重新進(jìn)行匹配。（3）重復(fù)上述過程，直到模式串與目標(biāo)串匹配結(jié)束，返回匹配結(jié)果。為便于理解，下面用一個具體的實(shí)例說明KMP算法的模式匹配過程。例如，目標(biāo)串s='acabaabaabcacbc'，模式串t='abaabc'，分別使用變量i和j（初始均為0）遍歷s和t，使用KMP算法判斷模式串t與目標(biāo)串s是否匹配的過程如下。4.3串的模式匹配算法（1）求解模式串t='abaabc'對應(yīng)的前綴數(shù)組next。①當(dāng)j=0時，next[0]=-1。②當(dāng)j=1時，串'a'的前綴和后綴都為空集，沒有相同的前綴子串和后綴子串，最長共有元素長度為0，故next[1]=0。③當(dāng)j=2時，串'ab'的前綴為{'a'}，后綴為{'b'}，沒有相同的前綴子串和后綴子串，最長共有元素長度為0，故next[2]=0。④當(dāng)j=3時，串'aba'的前綴為{'a','ab'}，后綴為{'a','ba'}，相同的前綴子串和后綴子串為{'a'}，最長共有元素長度為1，故next[3]=1。⑤當(dāng)j=4時，串'abaa'的前綴為{'a','ab','aba'}，后綴為{'a','aa','baa'}，相同的前綴子串和后綴子串為{'a'}，最長共有元素長度為1，故next[4]=1。⑥當(dāng)j=5時，串'abaab'的前綴為{'a','ab','aba','abaa'}，后綴為{'b','ab','aab','baab'}，相同的前綴子串和后綴子串為{'ab'}，最長共有元素長度為2，故next[5]=2。4.3串的模式匹配算法（2）借助前綴數(shù)組next進(jìn)行模式串t與目標(biāo)串s的匹配。①

第1趟從i=0、j=0開始依次匹配。當(dāng)i=1、j=1時，匹配失敗。此時，i不變，前綴數(shù)組next中下標(biāo)j=1所對應(yīng)的元素為0，則將模式串t向右移動，直到j(luò)指向下標(biāo)為0的字符。②第2趟從i=1、j=0開始依次匹配，可以發(fā)現(xiàn)匹配失敗。此時，前綴數(shù)組next中下標(biāo)j=0所對應(yīng)的元素為-1，故須將i和j同時加1。4.3串的模式匹配算法③第3趟從i=2、j=1開始依次匹配，可以發(fā)現(xiàn)匹配失敗。此時，i不變，前綴數(shù)組next中下標(biāo)j=1所對應(yīng)的元素為0，則將模式串t向右移動，直到j(luò)指向下標(biāo)為0的字符。④第4趟從i=2、j=0開始依次匹配。當(dāng)i=7、j=5時，匹配失敗。此時，i不變，前綴數(shù)組next中下標(biāo)j=5所對應(yīng)的元素為2，則將模式串t向右移動，直到j(luò)指向下標(biāo)為2的字符。⑤第5趟從i=7、j=2開始依次匹配。當(dāng)i=10、j=5時，模式串t的每個字符依次和目標(biāo)串s的一個連續(xù)的字符序列相等，此時匹配成功。4.3串的模式匹配算法defgetNext(t,next): #求解前綴數(shù)組nextj=0k=-1next[0]=-1whilej<len(t)-1:ifk==-1ort[j]==t[k]: #變量j遍歷后綴，變量k遍歷前綴

j=j+1k=k+1next[j]=k【算法描述】4.3串的模式匹配算法k=next[k] defkmp(str1,str2,pos):

#利用KMP算法進(jìn)行串的模式匹配

max=100 next=[None]*max #設(shè)置前綴數(shù)組next的大小

getNext(str2,next) #調(diào)用getNext()方法求解模式串的前綴數(shù)組nexti=pos

#目標(biāo)串的遍歷變量

j=0

#模式串的遍歷變量

whilei<len(str1)andj<len(str2):ifj==-1orstr1[i]==str2[j]:i+=1

#目標(biāo)串的遍歷變量后移

j+=1

#模式串的遍歷變量后移4.3串的模式匹配算法else:j=next[j] #j回溯

ifj==len(str2):returni-len(str2)#匹配成功，返回模式串在目標(biāo)串的起始位置

else:return-1 #匹配失敗，返回-1【算法分析】假設(shè)目標(biāo)串的長度為n，模式串的長度為m，在KMP算法匹配過程中，目標(biāo)串的下標(biāo)無須回溯，整個匹配過程中，對目標(biāo)串僅需從頭至尾掃描一遍，故KMP算法的時間復(fù)雜度為O(n)。但KMP算法匹配前需計(jì)算前綴數(shù)組next，其時間復(fù)雜度為O(m)。因此，KMP算法的總體時間復(fù)雜度為O(n+m)。同步訓(xùn)練編輯文本文件【問題描述】設(shè)計(jì)一個算法，在指定目錄下創(chuàng)建一個文本文件，并在該文件中寫入串，然后輸出指定串在該文件中的行號及位置?！締栴}分析】首先在目錄“D:\”下創(chuàng)建一個名為“testfile.txt”的文件，并寫入串（見下圖），然后計(jì)算指定串在“testfile.txt”文件中的行號，最后使用BF算法進(jìn)行模式匹配，以確定指定串在具體行中的位置。同步訓(xùn)練編輯文本文件【代碼實(shí)現(xiàn)】defbf(str1,str2): #BF算法

i=0 #i為目標(biāo)串str1的起始位置

j=0 #j為模式串str2的起始位置

whilei<len(str1)andj<len(str2):ifstr1[i]==str2[j]:i+=1j+=1else: #變量回溯

i=i-j+1j=0同步訓(xùn)練編輯文本文件ifj==len(str2): returni-len(str2)#匹配成功，返回str2的首字符在str1中的位置

else:return-1 #匹配失敗，返回-1deftext_create(name,msg): #創(chuàng)建文本文件

desktop_path='D:/' #新創(chuàng)建的文本文件的存放路徑

full_path=desktop_path+name+'.txt'#文本文件的絕對路徑

file=open(full_path,'w') #打開文本文件

file.write(msg) #向文本文件中寫入串

#在文本文件中查找串：path為文件的絕對路徑，name為待匹配的串同步訓(xùn)練編輯文本文件defseek_in_txt_name(path,name):withopen(path)asf: #打開文本文件

forsinf:flag=True #匹配標(biāo)記

ifnameins: #判斷是否有待