【正文】 next[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。9．解法同題6，其next和nextval 值分別為011123121231和011013020131。11．next數(shù)組值為011234567 改進(jìn)后的next數(shù)組信息值為010101017。13．next定義見題上面6和下面題20。14．（1）S的next與nextval值分別為012123456789和002002002009，p的next與nextval值分別為012123和002003。（p的next函數(shù)值為0111232）。p的next和nextval值分別為01112212321和01102201320。（next函數(shù)值為01123） （2）利用所得nextval數(shù)值，手工模擬對(duì)s的匹配過程，與上面16題類似，為節(jié)省篇幅，故略去。19．第4行的p[J]=p[K]語(yǔ)句是測(cè)試模式串的第J個(gè)字符是否等于第K個(gè)字符，如是，則指針J和K均增加1，繼續(xù)比較。 該算法在最壞情況下的時(shí)間復(fù)雜度O（m2）。 （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。21．這里失敗函數(shù)f，即是通常講的模式串的next函數(shù)，其定義見本章應(yīng)用題的第6題。模式串的next函數(shù)值，只依賴于模式串，和主串無關(guān)，可以預(yù)先求出。在經(jīng)常發(fā)生“部分匹配”和主串很大不能一次調(diào)入內(nèi)存時(shí)，優(yōu)點(diǎn)特別突出。這樣，因jk最小，即模式串向右滑動(dòng)的位數(shù)最小，避免因右移造成的可能匹配的丟失。24．（1）s1和s2均為空串；（2）兩串之一為空串；（3）兩串串值相等（即兩串長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相同）。2題中所給操作的含義如下：//：連接函數(shù)，將兩個(gè)串連接成一個(gè)串substr（s,i,j）：取子串函數(shù)，從串s的第i個(gè)字符開始，取連續(xù)j個(gè)字符形成子串replace（s1,i,j,s2）：置換函數(shù)，用s2串替換s1串中從第i個(gè)字符開始的連續(xù)j個(gè)字符本題有多種解法，下面是其中的一種：（1） s1=substr（s,3,1） //取出字符：‘y’（2） s2=substr（s,6,1） //取出字符：‘+’（3） s3=substr（s,1,5） //取出子串：‘(xyz)’（4） s4=substr（s,7,1） //取出字符：‘*’（5） s5=replace（s3,3,1,s2）//形成部分串：‘（x+z）’（6） s=s5//s4//s1 //形成串t即‘（x+z）*y’初始值i和j均為0。否則，當(dāng)imn則為匹配失敗。本算法求字符串t在字符串s中的第一次出現(xiàn)，如是，輸出子串在s中的位置，否則輸出0。 while (i=mn amp。 j=n1) if (s[i]==t[j]){i++。} //對(duì)應(yīng)字符相等，指針后移。j=0。 if(i=mn amp。 j==n) {printf(“t在s串中位置是%d”,in+1)。}//匹配成功else return(0)。 int m,n,i。m,amp。 //輸入兩字符串的長(zhǎng)度 scanf(“%s”,s)。 //輸入子串 i=index(s,t,m,n)。若匹配成功，最佳情況是s串的第0到第n1個(gè)字符與t匹配，時(shí)間復(fù)雜度為o（n）；匹配成功的最差情況是，每次均在t的最后一個(gè)字符才失敗，直到s串的第mn個(gè)字符成功，其時(shí)間復(fù)雜度為o（（mn）*n），即o（m*n）。之所以串s的指針i最大到mn，是因?yàn)樵趍n之后,所剩子串長(zhǎng)度已經(jīng)小于子串長(zhǎng)度n，故不必再去比較。另外，根據(jù)子串的定義，返回值in+1是子串在主串中的位置，子串在主串中的下標(biāo)是in。從左到右掃描字符串，初次碰到數(shù)字字符時(shí)，作為一個(gè)整數(shù)的開始?！nt CountInt（）// 從鍵盤輸入字符串，連續(xù)的數(shù)字字符算作一個(gè)整數(shù)，統(tǒng)計(jì)其中整數(shù)的個(gè)數(shù)。ch）；// 從左到右讀入字符串　while（ch!=‘’） //‘’是字符串結(jié)束標(biāo)記　　if（isdigit（ch））// 是數(shù)字字符　　｛num=０； // 數(shù)初始化　　　while（isdigit（ch）amp。 ch!=‘’）// 拼數(shù)　　?。鹡um=num＊10+‘ch’‘０’；　　　　scanf（“％c”，amp。ch）； // 若拼數(shù)中輸入了‘’，則不再輸入　　 ｝// 結(jié)束while（ch！＝‘’）　printf（“共有%d個(gè)整數(shù)，它們是：”i）；　for（j=０；ji；j++）?。鹥rintf（“%6d”，a[j]）；　 　if（（j+1）％10==0）printf（“\n”）；} // 每10個(gè)數(shù)輸出在一行上｝// 算法結(jié)束［算法討論］假定字符串中的數(shù)均不超過32767，否則，需用長(zhǎng)整型數(shù)組及變量。int LongestString(char s[],int n)//串用一維數(shù)組s存儲(chǔ)，長(zhǎng)度為n，本算法求最長(zhǎng)重復(fù)子串，返回其長(zhǎng)度。 //index記最長(zhǎng)的串在s串中的開始位置，max記其長(zhǎng)度 int length=1,i=0,start=0。 length++。 index=start。start=i。 //初始化下一重復(fù)子串的起始位置和長(zhǎng)度}printf(“最長(zhǎng)重復(fù)子串的長(zhǎng)度為%d，在串中的位置%d\n”，max,index)。}//算法結(jié)束[算法討論]算法中用in1來控制循環(huán)次數(shù)，因C數(shù)組下標(biāo)從0 開始，故長(zhǎng)度為n的串，其最后一個(gè)字符下標(biāo)是n1，當(dāng)i最大為n2時(shí)，條件語(yǔ)句中s[i+1]正好是s[n1]，即最后一個(gè)字符。算法的時(shí)間復(fù)雜度為O(n），每個(gè)字符與其后繼比較一次。我們先討論第一種形式的替換。最后將t串復(fù)制到s串的合適位置上。int replace(strtp s,t,int i,j)//s和t是用一維數(shù)組存儲(chǔ)的串，本算法將s串從第i個(gè)字符開始的連續(xù)j個(gè)字符用t串置換，操作成功返回1，否則返回0表示失敗。exit(0)。if(j) //若s串被替換的子串長(zhǎng)度小于t串長(zhǎng)度，則s串部分右移, for(k=。k) [k+]=[k]。 for(k=i1+j。k++) [k()]=[k]。k。 //將t串復(fù)制到s串的適當(dāng)位置if(j) =()。}//算法結(jié)束[算法討論]若允許使用另一數(shù)組，在檢查合法性后，可將s的第i個(gè)（不包括i）之前的子串復(fù)制到另一子串如s1中，再將t串接到s1串后面,然后將s的第i+j直到尾的部分加到s1之后。主要語(yǔ)句有：for(k=0。k++) [k]=[k]。k。for(k=。k)。k+。//將結(jié)果串放入s。該操作的意義是用串v替換所有在串s中出現(xiàn)的和非空串t相等的不重疊的子串。void replace(string s,t,v)//本算法是串的置換操作，將串s中所有非空串t相等且不重復(fù)的子串用v代替。//判斷s是否有和t相等的子串 if(i!=0)//串s中包含和t相等的子串 {creat(temp,”)。 m=length(t)。 //求串t和s的長(zhǎng)度 while(i!=0) {assign(temp,concat(temp,substr(s,1,i