【正文】 素是字符串（長4），將查找元素存放在一維數(shù)組中。) {q++。}while(*p!=’\0’amp。 //creat操作是將串常量（此處為空串）賦值給temp。 //將s1第i個字符前的子串復(fù)制到s1，這時k=i1for(k=0。k=i+j1。length=1。｛int i=0，a[]； // 整數(shù)存儲到數(shù)組a，i記整數(shù)個數(shù)　scanf（“％c”，amp。 scanf(“%d%d”,amp。{int i=0,j=0。進行模式匹配時，若主串第i個字符與模式串第j個字符發(fā)生失配，主串指針i不回溯，和主串第i個字符進行比較的是模式串的第next[j]個字符。串p的next函數(shù)值為：01212345634?！。常顑?yōu)的T(m,n)是O（n）?！? (2) setnull (exp) //串exp初始化為空串。t串用j指針（1=j=）。故選B。amp。 (11) pop(s) //操作符取出后，退棧。按這種方法，本題比較18次成功。（next函數(shù)值為01123） （2）利用所得nextval數(shù)值，手工模擬對s的匹配過程，與上面16題類似，為節(jié)省篇幅，故略去。24．（1）s1和s2均為空串；（2）兩串之一為空串；（3）兩串串值相等（即兩串長度相等且對應(yīng)位置上的字符相同）。j=0。若匹配成功，最佳情況是s串的第0到第n1個字符與t匹配，時間復(fù)雜度為o（n）；匹配成功的最差情況是，每次均在t的最后一個字符才失敗，直到s串的第mn個字符成功，其時間復(fù)雜度為o（（mn）*n），即o（m*n）。int LongestString(char s[],int n)//串用一維數(shù)組s存儲，長度為n，本算法求最長重復(fù)子串，返回其長度。我們先討論第一種形式的替換。k。k+。 //在新s串中再找串t的位置}assign(s,contact(temp,s))。) {printf(%d位置大于字符串s的長度,pos)。 p。若檢索成功，返回name在string中的下標，否則返回1。\039。8.[題目分析]本題要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按給定長度n格式化成兩端對齊的字符串”，即長度為n且首尾字符不得為空格字符。\039。amp。\039。void Count（）//統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。 A[i++] = ch。39。 //形成串s2s3=concat(s1,s2)。這四種數(shù)據(jù)結(jié)構(gòu)均定義成結(jié)構(gòu)體形式，數(shù)據(jù)部分用一維數(shù)組存儲，同時用指針指出數(shù)據(jù)的個數(shù)。在運算符（‘+’，‘*’，‘（’，‘）’）填入TOKEN表時，TOKEN表的addr域沒意義，為了程序統(tǒng)一，這里填入了’\0’。 i++。bcb39。 和s39。.39。return (1)。 //置s2字符串結(jié)束標記 } *q=s3。 39。\039。,即字符與39。）的ASCII值，變成數(shù)，先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分數(shù)，直到字符串結(jié)束，得到結(jié)果。//字符串長4}node。\039。i++。 //求串t和s的長度 while(i!=0) {assign(temp,concat(temp,substr(s,1,i1),v))。for(k=。 for(k=i1+j。}//算法結(jié)束[算法討論]算法中用in1來控制循環(huán)次數(shù)，因C數(shù)組下標從0 開始，故長度為n的串，其最后一個字符下標是n1，當i最大為n2時，條件語句中s[i+1]正好是s[n1]，即最后一個字符。 ch!=‘’）// 拼數(shù)　　?。鹡um=num＊10+‘ch’‘０’；　　　　scanf（“％c”，amp。 //輸入兩字符串的長度 scanf(“%s”,s)。 j=n1) if (s[i]==t[j]){i++。在經(jīng)常發(fā)生“部分匹配”和主串很大不能一次調(diào)入內(nèi)存時，優(yōu)點特別突出。（p的next函數(shù)值為0111232）。?。矗畼闼氐哪Ｊ狡ヅ洌˙rute－Force）時間復(fù)雜度是Ｏ（m＊n），KMP算法有一定改進，時間復(fù)雜度達到Ｏ（m＋n）。 (5) sempty (s) //判棧s是否為空。若該子串長度大于已求出的最長公共子串（初始為０），則最長公共子串的長度要修改。二、判斷題1.√2.√3.√程序（a）：（1）（i+k=）AND(j+k=) AND(s[i+k]=t[j+k]) //如果在s和t的長度內(nèi)，對應(yīng)字符相等，則指針k 后移（加1）。 (6) succ := false //若讀出ch是操作數(shù)且棧為空，則按出錯處理。本題也可采用從后面匹配的方法，即從右向左掃描，比較６次成功。（2）利用KMP(改進的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)16．KMP算法的時間復(fù)雜性是O（m+n）。22．失敗函數(shù)（即next）的值只取決于模式串自身，若第j個字符與主串第i個字符失配時，假定主串不回溯，模式串用第k（即next[j]）個字符與第i個相比，有‘ p1…pk1’=‘pjk+1…pj1’，為了不因模式串右移與主串第i個字符比較而丟失可能的匹配，對于上式中存在的多個k值，應(yīng)取其中最大的一個。j++。 //輸入主串 scanf(“%s”,t)。ch）；　　　 ｝　　　a[i]=num；i++；　　　if（ch!=‘’）scanf（“%c”，amp。子串長度的初值數(shù)為1，表示一個字符自然等于其身。k=。ki1+j。//用串v替換t形成部分結(jié)果 assign(s,substr(s,i+m,nim+1))。} //查pos位置 //若pos小于串s長度，則查到pos位置時，i=pos。 for(j=i。非遞歸過程如下：int binsearch(node string []。long atoi(char X[]) //一數(shù)字字符串存于字符數(shù)組X中，本算法將其轉(zhuǎn)換成數(shù){long num=0。039。) {printf(字符串s1為空串或空格串\n)。 ) //若最后一個字符為空格，則需向后找到第一個非空格字符 {p 。p++。 //兩串相等}//算法結(jié)束10.［問題分析］由于字母共26個，加上數(shù)字符號10個共36個，所以設(shè)一長36的整型數(shù)組，前10個分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。) //規(guī)定39。39。后是39。 }//while i。本題是表達式處理的簡化情況（只有3個單字母變量，常量只有0..9，操作符只4個），若是真實情況，所用數(shù)據(jù)結(jié)構(gòu)要相應(yīng)變化。 //i先從’\0’后退，是第偶數(shù)字符的個數(shù) while(i0) s[j++]=stk[i] //將第偶數(shù)個字符逆序填入原字符數(shù)組}14.[題目分析]本題是對字符串表達式的處理問題，首先定義4種數(shù)據(jù)結(jié)構(gòu)：符號的類碼，符號的TOKEN 表示，變量名表NAM