華北水利學院數(shù)據(jù)結構課件第四章

華北水利學院數(shù)據(jù)結構課件第四章2024/3/30華北水利學院數(shù)據(jù)結構課件第四章問題的提出查毒程序搜索引擎華北水利學院數(shù)據(jù)結構課件第四章1.串的邏輯結構串：由零個或多個任意字符組成的有限序列。串長度：串中所包含的字符個數(shù)?？沾洪L度為0的串，記為：""。非空串通常記為：

S=“a1a2…an”

其中：S是串名，雙引號是定界符，雙引號引起來的部分是串值，ai（1≤i≤n）是一個任意字符。華北水利學院數(shù)據(jù)結構課件第四章1.串的邏輯結構兩個串相等：如果兩個串的長度相等且對應字符都相等。子串：串中任意連續(xù)的字符組成的子序列稱為該串。主串：包含子串的串。子串的第一個字符在主串中的序號稱為子串的位置。華北水利學院數(shù)據(jù)結構課件第四章順序串：用數(shù)組來存儲串中的字符序列。（1）用一個變量來表示串的長度。2.串的存儲結構——順序串如何表示串的長度？華北水利學院數(shù)據(jù)結構課件第四章順序串：用數(shù)組來存儲串中的字符序列。（2）在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結符

。

2.串的存儲結構——順序串如何表示串的長度？華北水利學院數(shù)據(jù)結構課件第四章順序串：用數(shù)組來存儲串中的字符序列。（3）用數(shù)組的0號單元存放串的長度，串值從1號單元開始存放。

2.串的存儲結構——順序串如何表示串的長度？華北水利學院數(shù)據(jù)結構課件第四章鏈接串：用鏈接存儲結構來存儲串。p552.串的存儲結構——鏈接串華北水利學院數(shù)據(jù)結構課件第四章3.串的基本操作串的鏈接串的比較串的復制習題4.4、4.5、4.6習題4.7。編寫一個函數(shù)來顛倒單詞在字符串里的出現(xiàn)順序。【《程序員面試攻略(第2版)》p81】例如，把字符串“Doordonot,thereisnotry.”轉(zhuǎn)換為“try.noistherenot,doorDo”。假設所有單詞都以空格為分隔符，標點符號也當做字母來對待。請對你的設計思路做出解釋，并對你的解決方案的執(zhí)行效率進行評估。華北水利學院數(shù)據(jù)結構課件第四章3.串的基本操作刪除特定字符。【《程序員面試攻略(第2版)》p78】用C語言編寫一個高效率的函數(shù)來刪除字符串里的給定字符。這個函數(shù)的調(diào)用模型如下所示：voidRemoveChars(charstr[],charremove[]);注意，remove中的所有字符都必須從str中刪除干凈。比如說，如果str是“BattleoftheVowels:HawaiiVS.Grozny”，remove是“aeiou”，這個函數(shù)將把str轉(zhuǎn)換為“BttlfthVwls:Hwvs.Grzny”。請對你的設計思路做出解釋，并對你解決方案的執(zhí)行效率進行評估。華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——模式匹配模式匹配：給定主串S="s1s2…sn"和模式T="t1t2…tm"，在S中尋找T的過程稱為模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失敗，返回0。華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——BF模式匹配算法基本思想：從主串S的第一個字符開始和模式T的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串S的第二個字符開始和模式T的第一個字符進行比較，重復上述過程，直到T中的字符全部比較完畢，則說明本趟匹配成功；或S中字符全部比較完，則說明匹配失敗。華北水利學院數(shù)據(jù)結構課件第四章例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第

1趟abcac

4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbabi=3，j=3失??；i回溯到2，j回溯到1ji第

1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第

3趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第

3趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

i=11，j=6，T中全部字符都比較完畢，匹配成功。第

6趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章1.在串S和串T中設比較的起始下標i和j；2.循環(huán)直到S或T的所有字符均比較完；2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個字符；2.2否則，將i和j回溯，準備下一趟比較；3.如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標；否則，匹配失敗，返回0；4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章intBFmatching(chars[],chart[]){i=1;j=1;

while(i<=s[0]&&j<=t[0]){if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}}

if(j>t[0])return(i-j+1);

elsereturn0;}4.串的應用——BF模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——BF模式匹配算法設串s長度為n，串t長度為m，在匹配成功的情況下，考慮兩種極端情況：最好情況：不成功的匹配都發(fā)生在串t的第一個字符。例如：s="aaaaabcd"t="bcd"設匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能情況共有n-m+1種，則：設從si開始與t串匹配成功的概率為pi，在等概率情況下pi=1/(n

m+1)，平均比較的次數(shù)是因此最好情況下的時間復雜度是O(n+m)。華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——BF模式匹配算法設串s長度為n，串t長度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串t的最后一個字符。例如：s="aaaaab"t="aaab“設匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)×m次，第i趟成功的匹配共比較了m次，所以總共比較了i×m次，因此平均比較的次數(shù)是一般情況下，m<<n，因此最壞情況下的時間復雜度是O(nm)。華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——BF模式匹配算法為什么BF算法時間性能低？在每趟匹配不成功時存在大量回溯，沒有利用已經(jīng)部分匹配的結果。如何在匹配不成功時主串不回溯？主串不回溯，模式就需要向右滑動一段距離。如何確定模式的滑動距離？華北水利學院數(shù)據(jù)結構課件第四章i=3，j=3失?。?/p>

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbab第

2趟abcac

4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章i=3，j=3失敗；

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbababcac

第

3趟4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

第

3趟iji=7，j=5失敗s4=t2;t1≠t2∴t1≠s4ababcabcacbababcac

第

4趟4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

第

3趟iji=7，j=5失敗s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

5趟4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章ababcabcacbababcac

第

3趟iji=7，j=5失敗s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

6趟匹配成功4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——KMP模式匹配算法結論：i可以不回溯，模式向右滑動到的新比較起點k，并且k僅與模式串T有關！需要討論兩個問題：①如何由當前部分匹配結果確定模式向右滑動的新比較起點k？②模式應該向右滑多遠才是最高效率的?華北水利學院數(shù)據(jù)結構課件第四章請抓住部分匹配時的兩個特征：（1）設模式滑動到第k個字符，則T1～Tk-1

＝Si-(k-1)

～Si-1

S="ababc

a

b

cacbab"T="a

b

cac"ikjS="ababc

a

bcacbab"T="ab

cac"ik4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章請抓住部分匹配時的兩個特征：兩式聯(lián)立可得：T1～Tk-1＝Tj-(k-1)

～Tj-1（2）則Tj-(k-1)～

Tj-1＝Si-(k-1)～

Si-1S="ababc

a

b

cacbab"T="a

b

cac"ikjiS="ababc

a

b

cacbab"T="a

b

cac"jk（1）設模式滑動到第k個字符，則T1～Tk-1

＝Si-(k-1)

～Si-1

4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章T1…Tk-1＝Tj-(k-1)…Tj-1說明了什么？（1）k

與

j

具有函數(shù)關系，由當前失配位置j，可以計算出滑動位置k（即比較的新起點）；（2）滑動位置k

僅與模式串T有關。從第1位往右經(jīng)過k-1位從j-1位往左經(jīng)過k-1位k＝max{k|1<k<j

且T1…Tk-1＝Tj-(k-1)…Tj-1}T1…Tk-1＝Tj-(k-1)…Tj-1的物理意義是什么？模式應該向右滑多遠才是最高效率的?4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章next[j]＝0當j＝1時//不比較max{k|1<k<j且T1…Tk-1=Tj-(k-1)…Tj-1}1其他情況令k=next[j]，則：next[j]函數(shù)表征著模式T中最大相同首子串和尾子串（真子串）的長度。可見，模式中相似部分越多，則next[j]函數(shù)越大，它既表示模式T字符之間的相關度越高，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復雜度就越低。4.串的應用——KMP模式匹配算法華北水利學院數(shù)據(jù)結構課件第四章4.串的應用——KMP模式匹配算法計算next[j]的方法：當j=1時，next[j]=0；//next[j]=0表示根本不進行字符比較當j>1時，next[j]的值為：模式串的位置從1到j-1構成的串中所出現(xiàn)的首尾相同的子串的最大長度加1。當無首尾相同的子串時next[j]的值為1。next[j]=1表示從模式串頭部開始進行字符比較華北水利學院數(shù)據(jù)結構課件第四章j=1時,next[j]＝0；j=2時,next[j]＝1；j=3時,t1≠t2，因此，k=1；j=4時,t1＝t3，因此，k=2；j=5時,t1＝t4，因此，k=2；以此類推。4.串的應用——KMP模式匹配算法j12345678模式串a(chǎn)ba