【正文】 主串指針i不回溯。 （3）在上面兩種情況外，發(fā)生失配時(shí)，主串指針i不回溯，在最壞情況下，模式串從第1個(gè)字符開始與主串第i個(gè)字符比較，以便不致丟失可能的匹配。第6行的p[J]=p[K]語句的意義是，當(dāng)?shù)贘個(gè)字符在模式匹配中失配時(shí)，若第K個(gè)字符和第J個(gè)字符不等，則下個(gè)與主串匹配的字符是第K個(gè)字符；否則，若第K個(gè)字符和第J個(gè)字符相等，則下個(gè)與主串匹配的字符是第K個(gè)字符失配時(shí)的下一個(gè)（即NEXTVAL[K]）。17．（1）p的nextval函數(shù)值為01010。 （2）利用BF算法的匹配過程： 利用KMP算法的匹配過程： 第一趟匹配： aabaabaabaac 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配： aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配： aabaabaabaac aabaac(i=9,j=6)第五趟匹配： aabaabaabaac aa(i=6,j=2)第六趟匹配： aabaabaabaac a(i=6,j=1)第七趟匹配： aabaabaabaac(成功) aabaac(i=13,j=7) 15．（1）p的nextval函數(shù)值為0110132。12．011122312。8．解法同題6，t串的next和nextval函數(shù)值分別為0111232和0110132。若失敗，模式串后移，再重復(fù)以上過程。開始求出最大公共子串的長度恰是串S2的長度，一般情況下，T(m,n) =O(m*n)?？崭翊怯煽崭窠M成的串，其長度等于空格的個(gè)數(shù)。四．應(yīng)用題?。保橇銈€(gè)至多個(gè)字符組成的有限序列。 (9) exp (10) gettop(s) //取棧頂操作符。 (4) push (s,ch) //如ch是運(yùn)算符，則入運(yùn)算符棧s。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch18．（1）initstack（s） /／棧s初始化為空棧。 s[i+k]==t[j+k] //所有注釋同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++15．（1）0 （2）next[k]16．（1）i：=i+1 （2）j:=j+1 (3)i:=ij+2 (4)j:=1?！〕绦颍╞）：(1) i+k= amp。程序中第三個(gè)（即最內(nèi)層）的WHILE循環(huán)，是當(dāng)s中某字符（s［i］）與t中某字符（t［j］）相等時(shí)，求出局部公共子串。11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’13．（1）char s[ ] (2) j++ (3) i = j14．[題目分析]本題算法采用順序存儲(chǔ)結(jié)構(gòu)求串s和串t的最大公共子串。為避免考試中的二意性，編者認(rèn)為第9題出得好。若字符串長度為n（n0），長為n的子串有1個(gè)，長為n1的子串有2個(gè)，長為n2的子串有3個(gè)，……，長為1的子串有n個(gè)。 注：子串的定義是：串中任意個(gè)連續(xù)的字符組成的子序列，并規(guī)定空串是任意串的子串，任意串是其自身的子串。但某些教科書上認(rèn)為“空串是任意串的子串”無意義，所以認(rèn)為選C。三．填空題1．(1) 由空格字符（ASCII值32）所組成的字符串 (2)空格個(gè)數(shù) 2．字符3．任意個(gè)連續(xù)的字符組成的子序列 4．5 (m+n)6．01122312 7．01010421 8．(1)模式匹配 (2)模式串9．(1)其數(shù)據(jù)元素都是字符(2)順序存儲(chǔ)(3)和鏈?zhǔn)酱鎯?chǔ)(4)串的長度相等且兩串中對(duì)應(yīng)位置的字符也相等10．兩串的長度相等且兩串中對(duì)應(yīng)位置的字符也相等。算法思想是對(duì)每個(gè)i（1=i=，即程序中第一個(gè)WHILE循環(huán)），來求從i開始的連續(xù)字符串與從j（1=j=，即程序中第二個(gè)ＷHILE循環(huán)）開始的連續(xù)字符串的最大匹配。 （2）con:=false //s和t對(duì)應(yīng)字符不等時(shí)置標(biāo)記退出 （3）j:=j+k //在t串中，從第j+k字符再與s[i]比較 （4）j:=j+1 //t串取下一字符（5）i：=i+1 //s串指針i后移（加1）。amp。后，判ch1是否等于ch2，得出真假結(jié)論。 (3) ch in opset //判取出字符是否是操作符。 (7) exp (8)ch //若ch是操作數(shù)且棧非空，則形成部分中綴表達(dá)式?！。玻崭袷且粋€(gè)字符，其ASCII碼值是32。串S2是串S1的子串，且在S1中的位置是1。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個(gè)字符，若不等，則模式串后移；若相等，再比較模式串的第一個(gè)字符，若第一個(gè)字符也相等，則從模式串的第二個(gè)字符開始，向右比較，直至相等或失敗。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出．?。叮Ｊ酱膎ext函數(shù)定義如下： 　　　next［j］= 根據(jù)此定義，可求解模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnext[j]0 1 1 1 2 2 3 1 2 3 4 5nextval[j]0 1 1 0 2 1 3 0 1 1 0 57．解法同上題6，其next和nextval值分別為0112123422和0102010422。11．next數(shù)組值為011234567 改進(jìn)后的next數(shù)組信息值為010101017。14．（1）S的next與nextval值分別為012123456789和002002002009，p的next與nextval值分別為012123和002003。p的next和nextval值分別為01112212321和01102201320。19．第4行的p[J]=p[K]語句是測試模式串的第J個(gè)字符是否等于第K個(gè)字符，如是，則指針J和K均增加1，繼續(xù)比較。 （2）當(dāng)主串第i個(gè)字符與模式串中第j個(gè)字符失配時(shí)，若主串i不回溯，則假定模式串第k個(gè)字符與主串第i個(gè)字符比較，k值應(yīng)滿足條件1kj并且‘p１…pk1’=‘pjk+1…pj1’，即k為模式串向后移動(dòng)的距離，k值有多個(gè)，為了不使向右移動(dòng)丟失可能的匹配，k要取大，由于max{k}表示移動(dòng)的最大距離，所以取max{k}，k的最大值為j1。模式串的next函數(shù)值，只依賴于模式串，和主串無關(guān)，可以預(yù)先求出。這樣，因jk最小，即模式串向右滑動(dòng)的位數(shù)最小，避免因右移造成的可能匹配的丟失。