KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下： 1．在串t和串s中，分别设比较的起始下标i=J=O 2．如果串t和串s都还有字符，则循环执行下列操作：
(1)如果j=-l或者t[i]-s[j]，则将i和j分别加1，继续比较t和s的下一个字符； (2)否则，将j向右滑动到next[j]的位置，即j=next[J]
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置(从1开始)；否则返回一1．
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。 【C代码】 (1)常量和变量说明 t，s：长度为Is的字符串 next:next数组，长度为Is (2)C程序 #include
void get_next(int*next,char*s,intIs){
Int i=0，j=-1；
next[0]=-1；/*初始化next[0]*／ while(i if(j=-1lls[i]=s[j]){／*匹配*／ j++； i++； if(s[i]一s[jl) next[i]-next[j]; else Next[i]=j； } else 第 11 页 共 11 页 j=next[j]； } } int kmp(int*next, char*t, char*s, int lt, int Is){ int i=0,j=0; while(i if(j=-1II2_){ i++; j++; } else{ (3): } if(j>=ls) Retum(4) else retum-1； } 【问题1】(8分) 根据题干说明，填充C代码中的空(1)～(4)。 【问题2】(2分) 根据题干说明和C代码，分析出kmp算法的时间复杂度为(5)(主串和子的长度分别为It和Is，用O符号表示)。 【问题3】(5分) 根据C代码，字符串“BBABBCAC”的next数组元素值为(6)(直接写素值，之间用逗号隔开)。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC则函数Kmp的返回值是(7)。 第 12 页 共 12 页 参考答案： 问题1：(1)：j 问题3：(6)：[-1,-1,1,-1,-1,2,0,0]，(7)6。 试题分析： 本题问题1根据KMP算法的伪代码描述进行推导。 根据伪代码中第2步可以推导(1)是判断字符串s是否还有字符，即j 根据伪代码第2。1步可以推导(2)是判断字符串t和字符串s当前位置的字符是否相同，即t[i]==s[j]。 根据伪代码第2。2步可以推导(3)是当第2。1步判断条件不满足时，改变j所指向的字符位置。即调用函数get_next(next,s,ls)，且j=next[j]。 根据伪代码第3步可以推导(4)是返回匹配的起始位置。由于当前i所指向字符串中匹配子串的最后一个字符的位置，且已知子串的长度为ls。(4)的代码为i+1-ls。 本题问题2是计算KMP算法的复杂度。 本题问题3中已知字符串“BBABBCAC”，则根据get_next()函数可以求得next数组的元素值为[-1,-1,1,-1,-1,2,0,0]。并计算得到起始位置为6。 试题六(共15分) 阅读下列说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】某发票(lnvoice)由抬头(Head)部分、正文部分和脚注(Foot)部分构成。现采用装饰(Decorator)模式实现打印发票的功能，得到如图6-1所示的类图。 第 13 页 共 13 页 【java代码】 class invoice{ Public void printInvoice(){ System.out.println(\} } Class Decorator extends Invoice{ Protected Invoice ticket; publicDecorator(lnvoicet){ ticket=t; } Public void printinvoice(){ if(ticket!=NULL) (1)； } } Class Foot Decoratorextends Decorator{ publicFootDecorator(lnvoicet){ super(t); } Public void printinvoice(){ Systent.out.println(\(2)； } } Class FootDecorator extends Decorator{ 第 14 页 共 14 页 publicFootDecorator(invoicet){ super(t); } publicvoidprintlnvoice(){ (3)； Systent.out.println(\} } Class test{ Public static void main(string[]args){ Invoice t = new Invioce(); Invoice ticket; Ticket=(4)； Ticket.Printinvoice(); Systent.out.println(“--------------“) Ticket=(5)； Ticket.Printinvoice(); } } 程序的输出结果为： Thisistheheaderoftheinvoice! Thisisthecontentoftheinvoice! Thisisthefootnoteoftheinvoice! ---------------------------- Thisistheheaderoftheinvoice! Thisisthefootnoteoftheinvoice 第 15 页 共 15 页 参考答案： (1)ticket.printInvoice() (2)ticket.printInvoice() (3)ticket.printInvoice() (4)new FootDecorator(newHeadDecorator(t)) (5)new FootDecorator(newHeadDecorator(newDecorator(null))) 第 16 页 共 16 页