第四章 串
一、选择题
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,即程序中第二个WHILE循环)开始的连续字符串的最大匹配。程序中第三个(即最内层)的WHILE循环,是当s中某字符(s[i])与t中某字符(t[j])相等时,求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为0),则最长公共子串的长度要修改。
程序(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的最后。
四.应用题
1.串是零个至多个字符组成的有限序列。从数据结构角度讲,串属于线性结构。与线性表的特殊性在于串的元素是字符。
2.空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。
3.最优的T(m,n)是O(n)。串S2是串S1的子串,且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度,一般情况下,T(m,n) =O(m*n)。
4.朴素的模式匹配(Brute-Force)时间复杂度是O(m*n),KMP算法有一定改进,时间复杂度达到O(m+n)。 本题也可采用从后面匹配的方法,即从右向左扫描,比较6次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移; 若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。 按这种方法,本题比较18次成功。
5.KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时,KMP算法的优点更为突出.
6.模式串的next函数定义如下:
next[j]=
根据此定义,可求解模式串t的next和nextval值如下:
j |
1 2 3 4 5 6 7 8 9 10 11 12 |
t串 |
a b c a a b b a b c a b |
next[j] |
0 1 1 1 2 2 3 1 2 3 4 5 |
nextval[j] |
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 值分别为011123121231和011013020131。
10.p1的next和nextval值分别为:0112234和0102102;p2的next和nextval值分别为:0121123和0021002。
11.next数组值为011234567 改进后的next数组信息值为010101017。
12.011122312。
13.next定义见题上面6和下面题20。串p的next函数值为:01212345634。
14.(1)S的next与nextval值分别为012123456789和002002002009,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值分别为01112212321和01102201320。
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])。
该算法在最坏情况下的时间复杂度O(m2)。
20.(1)当模式串中第一个字符与主串中某字符比较不等(失配)时,next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较,主串当前指针应后移至下一字符,再和模式串中第一字符进行比较。
(2)当主串第i个字符与模式串中第j个字符失配时,若主串i不回溯,则假定模式串第k个字符与主串第i个字符比较,k值应满足条件1<k<j并且‘p1…pk-1’=‘pj-k+1…pj-1’,即k为模式串向后移动的距离,k值有多个,为了不使向右移动丢失可能的匹配,k要取大,由于max{k}表示移动的最大距离,所以取max{k},k的最大值为j-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