第4章串 作业(参考答案).doc

第四章 串 作业参考答案：1、简述空串和空格串（或称空格符串）的区别？1）空串是指不包括任何字符的串，空格串指包含若干个空格字符的字符串；2）空串长度为零，空格串长度为所包括的空格字符的个数。2、设s=I AM A STUDENT ,t=GOOD,q=WORKER.求：1） StrLength（s）2） StrLength（t）3） SubString（s，8，7）4） SubSting（t，2，1）5） Index（s，A）6） index（s，t）7） Replace（s，STUDENT，q）8） Concat（SubString（s，6，2）,Concat（t，SubString（s，7，8） 答：1) StrLength（s）=142) StrLength（t）=43) SubString（s，8，7） = STUDENT4) SubSting（t，2，1） = O5) Index（s，A）= 36) index（s，t） = 07) Replace（s，STUDENT，q） = I AM A WORKER 8) Concat（SubString（s，6，2）,Concat（t，SubString（s，7，8） = A GOOD STUDENT3、若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行 concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其结果是多少？答：ABC#G1234 4、下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。请将空格处填上正确的语句。void maxcomstr(orderstring *s,*t; int index, length) int i,j,k,length1,con; index=0;length=0;i=1; while (i=s.len) j=1; while(jlength) index=i; length=length1; (3)_; else (4) _; (5) _ 提示：算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1=i=s.len）。t串用j指针（1=j=t.len）。算法思想是对每个i（1=i=s.len，即程序中第一个while循环），来求从i开始的连续字符串与从j（1=j=t.len，即程序中第二个while循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的while循环，是当s中某字符（si）与t中某字符（tj）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为），则最长公共子串的长度要修改。程序：(1) i+k=s.len & j+k=t.len & si+k=tj+k /如果在s和t的长度内，对应字符相等，则指针k 后移（加1）(2) con=0 /s和t对应字符不等时置标记退出(3) j+=k /在t串中，从第j+k字符再与si比较(4) j+ /t串取下一字符(5) i+ /s串指针i后移（加1）。5、（选作）令s=aaab，t=abcabaa，u=abcaabbabcabaacbacba。 试分别求出它们的next函数值和nextval函数值。答：对s=aaab: next = 0, 1, 2, 3 nextval = 0, 0, 0, 3对t=abcabaa: next = 0, 1, 1, 1,2,3,2 nextval = 0,1,1,0,1,3,2对s=abcaabbabcabaacbacba:next = 0,1,1,1