計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第13章

PAGE1第13章 字符串匹配用樸素的匹配算法找出以下模式在所給文本串中所有合法移位：P=abba，T=abcaabbababba。解：下面圖示了在逐個(gè)移位下匹配的情況。移位4和9是合法移位。TT:abcaabbababbaP:abba(a)移位0，不匹配T:abcaabbababbaP:abbaT:abcaabbababbaP:abba(b)移位1，不匹配(c)移位2，不匹配T:abcaabbababbaP:abba(d)移位3，不匹配TT:abcaabbababbaP:abba(e)移位4，匹配T:abcaabbababbaP:abba(f)移位5，不匹配T:abcaabbababbaP:abba(g)移位6，不匹配T:abcaabbababbaP:abba(h)移位7，不匹配T:T:abcaabbababbaP:abba(i)移位8，不匹配T:abcaabbababbaP:abba(j)移位9，匹配假設(shè)模式P中沒有相同的字符，請(qǐng)把樸素的匹配算法改進(jìn)為復(fù)雜度為O(n)的算法。解：主要的改進(jìn)是，當(dāng)移位為s時(shí)所進(jìn)行的一輪匹配結(jié)束時(shí)，不論成功與否，下一輪的匹配不需要從這一輪已經(jīng)匹配過的字符開始。如下圖所示，如果這一輪匹配在P[i]失敗，因?yàn)槟Ｊ絇中沒有相同的字符，那么下一輪應(yīng)從T[s+i]開始，即下一個(gè)可能的移位為s+i-1。這里有個(gè)特殊情況，就是如果i=1，這一輪匹配在P[1]就失敗，那么下一輪應(yīng)從T[s+2]開始，即移位更新為s+1。改進(jìn)后的樸素的匹配算法如下：Improved-Naive-Matcher(T[1..n],P[1..m]) //P[1..m]中字符不同s0whilesn-m i1 whileimandP[i]=T[s+i] ii+1 endwhile ifi>1 then ifi=m+1 thenprint“avalidshift”s endif ss+i–1 //如果i=m+1，ss+m也正確 else ss+1 //這時(shí)，必有i=1，P[1]T[s+1] endifendwhileEnd與樸素的匹配算法一樣，對(duì)一個(gè)給定移位s，算法將模式P[1..m]中字符逐個(gè)與T[s+1..s+m]中字符進(jìn)行匹配。由上面討論，算法對(duì)每一個(gè)可能的移位都做了匹配，所以算法正確。下面我們證明以下命題：任何一個(gè)文本中字符，算法最多只需做2次比較。更準(zhǔn)確地說，如果一個(gè)文本中字符x在第一次比較時(shí)匹配于P中一個(gè)字符，那么算法不會(huì)再比較它。如果它在第一次比較時(shí)不匹配于P中一個(gè)字符，那么最多再被比較一次。證明：假設(shè)字符x是在移位s時(shí)被第一次比較。我們分3種情況來證明。如果這一輪匹配是成功匹配，下一輪檢查的移位是s+m，那么，這一輪匹配中檢查過的文本中的字符，包括x將不會(huì)在以后再被檢查。命題正確。如果是不成功匹配，并且P[1]T[s+1](第7行中i=1)。那么下一輪檢查的移位是s+1。這一輪中只檢查了一個(gè)字符，即x=T[s+1]，它將不會(huì)在以后再被檢查。命題正確。如果是不成功匹配，并且第7行中i>1。這表明這一輪中有i-1個(gè)字符成功匹配，P[1..i-1]=T[s+1..s+i-1]，但是，P[i]T[s+i]，下一輪檢查的移位是s+i-1。因此，這一輪中成功匹配的(i-1)個(gè)子符T[s+1..s+i-1]將不會(huì)在以后再被檢查。如果xT[s+1..s+i-1]，命題得證。否則，必有x=T[s+i]P[i]，并且x會(huì)在下一輪中與P[1]進(jìn)行比較。從算法知，下一輪中x的第二次比較，不論x=P[1]或xP[1]，x都不會(huì)參加再下一輪的匹配。命題正確。因?yàn)樗惴ǖ闹饕僮骶褪菍⑽谋局凶址c模式中字符相配，由命題知，每個(gè)字符最多只要比較兩次，而每次比較只需O(1)時(shí)間，所以上述改進(jìn)后的樸素的匹配算法的復(fù)雜度是O(n)。假設(shè)P=29，T=3294162968，并選用q=13作為模數(shù)。請(qǐng)用Rabin-Karp算法計(jì)算Pmodq，t0modq，t1modq，…，t8modq。在完成(a)部分工作后，Rabin-Karp需要做幾次模式匹配去檢查移位合法性？其中又有幾次是非法的呢？解：(a)pmodq=29mod13=3， t0modq=32mod13=6， t1modq=29mod13=3，(真)t2modq=94mod13=3，(偽)t3modq=41mod13=2，t4modq=16mod13=3，(偽)t5modq=62mod13=10，t6modq=29mod13=3，(真)t7modq=96mod13=5，t8modq=68mod13=3，(偽)(b) Rabin-Karp需要做5次模式匹配，其中3次為假，2次為真。(a)假設(shè)P=aaba，構(gòu)造字符串匹配用的有限狀態(tài)自動(dòng)機(jī)。用(a)部分中的自動(dòng)機(jī)對(duì)文本T=baababbaabab進(jìn)行匹配操作。解：(a)aa0123baaab4babb(b) 這題的文本串有12個(gè)字母。下面表格列出了用自動(dòng)機(jī)的狀態(tài)函數(shù)掃描每個(gè)字符T[i]，i=1,2,…,12,后所得的狀態(tài)q值并注明找到合法移位時(shí)當(dāng)前字符的位置。算法在掃描字符T[5]和T[11]后發(fā)現(xiàn)兩處成功匹配，其合法移位分別是1和7。i初始123456789101112T[i]--baababbaabab狀態(tài)q0012340012340合法移位17--(a)假設(shè)P=acbac，構(gòu)造字符串匹配用的有限狀態(tài)自動(dòng)機(jī)。(b)用(a)部分中的自動(dòng)機(jī)對(duì)文本T=bacbacbacaab進(jìn)行匹配操作。解：(a)aaa0123bcaac4bbc5b,cab,cabc(b) 這題的文本串有12個(gè)字母。下面表格列出了用自動(dòng)機(jī)的狀態(tài)函數(shù)掃描每個(gè)字符T[i]，i=1,2,…,12,后所得的狀態(tài)q值并注明找到合法移位時(shí)當(dāng)前字符的位置。算法在掃描字符T[6]和T[9]后發(fā)現(xiàn)兩處成功匹配，其合法移位分別是1和4。i初始123456789101112T[i]--bacbacbacaab狀態(tài)q0012345345110合法移位14假設(shè)P=acbacacbaac，計(jì)算它的前綴函數(shù)。解：下面表格列出了P的每一個(gè)前綴的前綴函數(shù)。i1234567891011P[i]acbacacbaac[i]00012123412假設(shè)P=ababcbababc，計(jì)算它的前綴函數(shù)。解： 下面表格列出了P的每一個(gè)前綴的前綴函數(shù)。i1234567891011P[i]ababcbababc[i]00120012345設(shè)P=aaba和T=aabaaabaabaabaa，用KMP算法計(jì)算所有合法移位。解：下面表格列出了P的每一個(gè)前綴的前綴函數(shù)。i1234P[i]aaba[i]0101基于這個(gè)前綴表，下面表格計(jì)算出到文本每一字符T[i]為止，最長(zhǎng)可有多少P的字符與文本T[1..i]的后綴匹配成功，也就是變量q值。在計(jì)算T[1..i]的q值時(shí)，如需要查找前綴函數(shù)表多次，表中列出這一過程。i初始123456789101112131415T[i]--aabaaabaabaabaa滑動(dòng)前綴q-11最終前綴q0123422342342342合法移位04710--更新后前綴q1111假設(shè)A[1..n]和B[1..n]是兩個(gè)等長(zhǎng)的文本。設(shè)計(jì)一個(gè)復(fù)雜度為O(n)的算法來確定是否文本B是文本A的循環(huán)移位并給出所有循環(huán)移位的位置。例如A=ababab，B=bababa，B是A的循環(huán)移位，位置為s=1,3,5。解：我們復(fù)制一個(gè)文本A，并把文本A和復(fù)制的文本A聯(lián)結(jié)成一個(gè)長(zhǎng)為2n的文本T，即T[1..n]=A[1..n]，T[n+1..2n]=A[1..n]。如果文本B是文本A的循環(huán)移位，那么文本B一定是文本T的一個(gè)子串，反之亦然。因此，我們可以把B作為模式，PB，然后用KMP算法將P與T進(jìn)行字符串匹配。顯然，所有小于n的合法移位s就是所有循環(huán)移位的位置。因?yàn)镵MP算法是O(n)的算法，所以這個(gè)解也是O(n)的算法。給定模式P[1..m]和文本T[1..n]，解釋如何通過計(jì)算Q=PT的前綴函數(shù)來確定P與T匹配的所有合法移位。這里Q[1..m+n]=PT是由P和T聯(lián)結(jié)而成，即Q[1..m]=P[1..m]，Q[m+1..m+n]=T[1..n]。例如，P=abc，T=baabca，那么Q=PT=abcbaabca。你可以假定Q的前綴函數(shù)已知。你只要設(shè)計(jì)一個(gè)從Q的前綴函數(shù)來計(jì)算P與T匹配的所有合法移位的算法。解：假定Q的前綴函數(shù)已知。我們對(duì)每一個(gè)Q的前綴，Q[1..i](1im+n)，順序確定模式P是否與Q[1..i]的后綴匹配。不難看出，P與Q[1..i]的后綴匹配，并有合法移位i–mm，當(dāng)且僅當(dāng)P與T匹配，并有合法移位i–2m。我們先確定P是否與Q[1..i]的后綴匹配。為此，我們查看[i]。我們有三種情況：[i]<m，1im+n。這種情況如下圖(a)所示，不論i<2m或i2m，模式P不與Q[1..i]的后綴匹配。PPTPTPTPTQ[i][i]<m的情況Q[i][i][i][i]=m，1im+n。這種情況下，模式P與Q[1..i]的后綴匹配。[i]=k>m，m<im+n。這種情況如下圖(c)所示。這時(shí)，模式P與Q[1..i]的后綴匹配當(dāng)且僅當(dāng)模式P與Q[1..k]的后綴匹配。TT[i]=k>m的情況PPTQ[i](上面的Q)[i]Q[k](下面的Q)由以上討論，我們有以下的算法。P-T-Matcher(m,n,[1..m+n],M[1..m+n]) //M[i]=yes表示P與Q[1..i]的后綴匹配fori?1tom+n if[i]<m then M[i]no else if[i]=m thenM[i]yes else k[i] M[i]M[k] endif endifendforfori?2mtom+n //現(xiàn)在考慮P與T的匹配 ifM[i]=yes thenprint“PatternoccursinTwithshift”i-2m endifendforEnd算法的正確性已經(jīng)在前面討論了。顯然算法有復(fù)雜度O(m+n)。改進(jìn)第13.3.2節(jié)中計(jì)算轉(zhuǎn)換函數(shù)(q,a)的算法使得其復(fù)雜度為O(m||)。解一：轉(zhuǎn)換函數(shù)(q,a)就是Pqa的后綴函數(shù)。一個(gè)直接的方法是像KMP算法那樣，先用一個(gè)O(m)算法算出前綴函數(shù)，然后算出轉(zhuǎn)換函數(shù)。我們?yōu)槊恳粋€(gè)q，從q=0到q=m，順序計(jì)算出(q,a)，即Pqa的后綴函數(shù)。我們考慮三種情況：如果q<m并且P[q+1]=a，則有(q,a)=q+1。這是因?yàn)镻q的后綴函數(shù)是P[1..q]，a=P[q+1]使得P[1..q+1]與Pqa相匹配，并且顯然是最長(zhǎng)的，所以有(q,a)=q+1。如果q<m，但是aP[q+1]，那么(q,a)必定小于q+1。設(shè)(q,a)=k+1<q+1，即Pk+1=Pka是Pqa的后綴函數(shù)，k<q。那么，Pk必定與Pq的后綴相配，并有P[k+1]=a。考慮Pq的前綴函數(shù)h=(q)。因?yàn)镻h是小于q的前綴中最大的與Pq后綴相配的P的前綴，kh，如下圖所示，Pka必定是Pha的后綴函數(shù)，所以有(q,a)=(h,a)=k+1。因?yàn)?h,a)已經(jīng)在早前算出，所以(q,a)可在O(1)時(shí)間得到。qq<m并且P[q+1]a的情形aP[1]’P[q]P[2]’P[k+1]=aP[1]’P[2]’P[k]

P[q+1]aP[1]’P[q]P[2]’

P[h+1]

P[h]

P[1]’P[2]’(q)=h<qk+1=(h,a)如果q=m，設(shè)(m)=h。對(duì)這種情況，顯然有(m,a)=(h,a)。所以(m,a)可在O(1)時(shí)間得到。根據(jù)以上分析，我們的算法如下。Transition-Function-using-prefix-function(P[1..m]，)[1..m]Prefix-Function(P[1..m]) //先算前綴函數(shù)foreacha ifP[1]=a then(0,a)1 else(0,a)0 e