第四章 串
一、选择题 1.B 2.E 3.C 4.A 5.C 6.A 7.1D 7.2F 8.B注 9.D 10.B 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题
1.√ 2.√ 3.√
三．填空题
1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串
9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等
10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\\0’ 13．（1）char s[ ] (2) j++ (3) i >= j
14．[题目分析]本题算法采用顺序存储结构求串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，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。
程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k])
//如果在s和t的长度，对应字符相等，则指针k 后移（加1）。 （2）con:=false //s和t对应字符不等时置标记退出
（3）j:=j+k //在t串中，从第j+k字符再与s[i]比较 （4）j:=j+1 //t串取下一字符
（5）i：=i+1 //s串指针i后移（加1）。
程序（b）：(1) i+k<=s.len && j+k<=t.len && 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:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0 17.程序中递归调用
（1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符 （2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch
18．（1）initstack（s） /／栈s初始化为空栈。
(2) setnull (exp) //串exp初始化为空串。
(3) ch in opset //判取出字符是否是操作符。
(4) push (s,ch) //如ch是运算符，则入运算符栈s。 (5) sempty (s) //判栈s是否为空。
(6) succ := false //若读出ch是操作数且栈为空，则按出错处理。
(7) exp (8)ch //若ch是操作数且栈非空，则形成部分中缀表达式。 (9) exp (10) gettop(s) //取栈顶操作符。 (11) pop(s) //操作符取出后，退栈。
(12) sempty(s) //将pre的最后一个字符（操作数）加入到中缀式exp的最
后。
四．应用题
１．串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。
２．空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。 ３．最优的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度，一般情况下，T(m,n) =O(m*n)。 ４．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。
５．KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入存且经常发生部分匹配时，KMP算法的优点更为突出．
６．模式串的next函数定义如下：
?0当j?1时?‘ p1...pk?1'?'pj?k?1...pj?1'}?max{k| 1?k?j 且?1其它情况next［j］=? 根据此定义，可求解模式串t的next和nextval值如下：
j t串 next[j] nextval[j] 当此集合不空时
1 2 3 4 5 6 7 8 9 10 11 12 a b c a a b b a b c a b 0 1 1 1 2 2 3 1 2 3 4 5 0 1 1 0 2 1 3 0 1 1 0 5 7．解法同上题6，其next和nextval值分别为0112123422和0102010422。
8．解法同题6，t串的next和nextval函数值分别为0111232和0110132。 9．解法同题6，其next和nextval 值分别为1和1。 10．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：
0121123和0021002。
11．next数组值为011234567 改进后的next数组信息值为010101017。 12．011122312。
13．next定义见题上面6和下面题20。串p的next函数值为：。 14．（1）S的next与nextval值分别为9和9，p的next与nextval值分别为012123和002003。 （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函数值为0110132。（p的next函数值为0111232）。
（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算法的时间复杂性是O（m+n）。
p的next和nextval值分别为和。 17．（1）p的nextval函数值为01010。（next函数值为01123）
（2）利用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇
幅，故略去。
18．模式串T的next和nextval值分别为0121123和0021002。
19．第4行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K个字符，如是，则指针J和K均增加1，继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K个字符和第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一个（即NEXTVAL[K]）。
2
该算法在最坏情况下的时间复杂度O（m）。 20．（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模
式串中第一字符进行比较。
（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1 （3）在上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第1个字符开始与主串第i个字符比较，以便不致丢失可能的匹配。 21．这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第6题。 进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。 该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入存时，优点特别突出。 22．失败函数（即next）的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，假定主串不回溯，模式串用第k（即next[j]）个字符与第i个相比，有‘ p1…pk-1’=‘pj-k+1…pj-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。 23．仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。 24．（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 25、题中所给操作的含义如下： //：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 本题有多种解法，下面是其中的一种： （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’ 五、算法设计 1、[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0=t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。 int index(char s[],t[],int m,n) //字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s 中的第一次出现，如是，输出子串在s中的位置，否则输出0。 {int i=0,j=0; while (i<=m-n && j<=n-1) if (s[i]==t[j]){i++;j++;} //对应字符相等，指针后移。 else {i=i-j+1;j=0;} //对应字符不相等，I回溯，j仍为0。 if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功 else return(0); //匹配失败 }//算法index结束 main ()//主函数 {char s[],t[]; int m,n,i; scanf(“%d%d”,&m,&n); //输入两字符串的长度 scanf(“%s”,s); //输入主串 scanf(“%s”,t); //输入子串 i=index(s,t,m,n); }//程序结束 [程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。 另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。 2.［问题分析］在一个字符串，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。 int CountInt（） // 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。 ｛int i=0，a[]； // 整数存储到数组a，i记整数个数 scanf（“％c”，&ch）；// 从左到右读入字符串 while（ch!=‘#’） //‘#’是字符串结束标记 if（isdigit（ch））// 是数字字符 ｛num=０； // 数初始化 while（isdigit（ch）&& ch!=‘#’）// 拼数 ｛num=num＊10+‘ch’-‘０’； scanf（“％c”，&ch）； ｝ a[i]=num；i++； if（ch!=‘#’）scanf（“%c”，&ch）； // 若拼数中输入了‘#’，则不再输入 ｝// 结束while（ch！＝‘#’） printf（“共有%d个整数，它们是：”i）；
算法与数据结构考研试题精析(第二版)第4章串答案
