算法与数据结构复习 第四章 字符串(详解)_设主串 t = abaabaabcabaabc,模式串 s = abaabc,采用 kmp 算法进行

第四章 字符串

书面作业

一、判断题

1、字符‘\0’的ASCII码值是0。 (T)

2、如果strcmp(s1,s2)返回的结果为0，表示字符串s1和s2不相同。 (F)

解析
C 库函数 int strcmp(const char *str1, const char *str2) 把 str1 所指向的字符串和 str2 所指向的字符串进行比较；

• 如果返回值 < 0，则表示 str1 小于 str2。
• 如果返回值 > 0，则表示 str2 小于 str1。
• 如果返回值 = 0，则表示 str1 等于 str2。

3、char *s=“C Language”;表示s是一个指向字符串的指针变量，把字符串的首地址赋予s。 (T)

4、C 语言中 , 字符串常量最后一个字符是结束标志 , 该结束符是’\0’ 。(T)

5、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。(F)
解析：
虽然每个字符都出现，但是字符顺序可能不同；

6、当用户要求输入的字符串中含有空格时,应使用的输入函数是 gets()。 (T)
解析：
在C语言中，scanf函数通过%s输入字符串时，空格不能输入，只有gets函数可以；

7、字符串在内存中的起始地址称为字符串的指针，可以定义一个字符指针变量指向一个字符
串。(T)

8、空串与空格串是相同的。 (F)
解析：
空串没有字符，空格是一个字符，尽管输出是一样的，但含义不同；

9、指针变量可以存放指针(地址)、数值和字符。 (F)
解析：
指针只能存放地址；

10、重载运算符可以保持原运算符的优先级和结合性不变。(T)

二、单选题

1、将两个字符串连接起来组成一个字符串时，选用函数（C）。
A. strlen( )
B. strcpy( )
C. strcat( )
D. strcmp( )
解析：

2、设有两个串p和 q，其中 q是p 的子串，求 q在p 中首次出现的位置的算法称为（C）。
A. 求子串
B. 联接
C. 模式匹配
D. 求串长

3、串也是一种线性表，只不过( A)。
A. 数据元素均为字符
B. 数据元素是子串
C. 数据元素数据类型不受限制
D. 表长受到限制

4、KMP 算法下，长为 n 的字符串匹配长度为 m 的字串的时间复杂度为 （B）
A. O（N）
B. O（M+N）
C. O(M+LOGN)
D. O(N+LOGM)

解析：
kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和 m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历O的每一个位置，然后从该位置开始和f进行匹配，但是这种方法的复杂度是 O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。
详解

5、下面关于串的叙述中，哪一个是不正确的 (B)
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储

6、若串 S=“software”，其子串的数目是 (B)
A. 8
B. 37
C. 36
D. 9

解析：
数目=8+7+6+5+4+3+2+1+1=37
空串也是字串；

7、串的长度是指 （B）
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数

8、下述对 C 语言字符数组的描述中错误的是（C）。
A. 字符数组可以存放字符串
B. 字符数组中的字符串可以整体输入、输出
C. 可以在赋值语句中通过赋值运算符"="对字符数组整体赋值
D. 不可以用关系运算符对字符数组中的字符串进行比较

解析：
字符串的赋值要用strcpy函数进行复制；

9、下面关于字符串的程序，其输出结果是 (B)

#include <iostream>
using namespace std;
void fun(char *s, char t) {
 	while (*s) {
 		if (*s == t)
		*s = t - 'a' + 'A';
 		s++;
 	} 
 }
int main() {
	char str[100] = "abcdefg", c = 'd';
 	fun(str, c);
	cout<< str <<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

A. abcdefg
B. abcDefg
C. ABCdEFG
D. ABCDEFG

10、串是一种特殊的线性表，其特殊性体现在(B)。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符

11、设串 s1=‟ABCDEFG‟，s2=‟PQRST‟，函数 con (x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是(D)。
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF

12、令 s=“abcabaa”，则它的特征向量 next 函数值和优化特征向量 nextval 函数值为(下标从 0开始)：(C )
A. next={0,1,1,1,2,3,2},nextval={0,1,1,0,1,2,1}
B. next={-1,0,0,-1,0,2,1},nextval={-1,0,0,0,1,2,1}
C. next={-1,0,0,0,1,2,1},nextval={-1,0,0,-1,0,2,1}
D. next={-1,0,0,0,1,2,1},nextval={-1,0,0,0,1,2,1}
解析：
特征向量next：

• 字符串的特征向量就是由字符串各位置上的特征数构成的一个向量。设字符串为P，令Pi为从字符串首字母到第i个位置的前缀，则字符串P的i位置上的特征数就是Pi的首尾非空真子串匹配的最大长度。
• 两种求法：
  • 第一种：第一位默认-1，之后的每一位是它之前的字符串最长公共前缀后缀长度；
  • 第二种：第一位默认0，第二位默认1，之后每一位是它之前的字符串最长公共前缀后缀长度+1;

优化特征向量 nextval:

• nextval的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致，如果一致则用s[next[i]]的nextval的值作为nextval[i]，如果不一致，则用next[i]做为nextval[i];

解题：
用方法一求next

• next[0]默认为-1，故next[0] = -1；

• next[1]是看s[1]之前的字符串“a”中重复的子串长度为0，故next[1] = 0；

• next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0，故next[2] = 0;

• next[3]是看s[3]之前的字符串"abc"中重复的子串长度为0，故next[3] = 0;

• next[4]是看s[4]之前的字符串"abca"中重复的子串长度，s[0]与s[3]重复，长度为1，故next[4] = 1;

• next[5]是看s[5]之前的字符串"abcab"中重复的子串长度，s[01]与s[34]重复，长度为2，故next[5] = 2;

• next[6]是看s[6]之前的字符串"abcaba"中重复的子串长度，s[0]与s[5]重复，长度为1，故next[6] = 1;

• 综上：next=[-1,0,0,0,1,2,1];

求nextval：

• nextval[0] = -1,和next[0]的值一样；
• nextval[1]，比较s[next[1]] 和 s[1]，next[1] = 0，s[0] = a，而s[1] = b，二者不一致，则nextval[1] = next[1] = 0；
• nextval[2]，比较s[next[2]] ?= s[2]，next[2] = 0，s[0] = a，而s[2] = c，二者不一致，则nextval[2] = next[2] = 0；
• nextval[3]，比较s[next[3]] ?= s[3]，next[3] = 0，s[0] = a，而s[3] = a，二者一致，则nextval[3] = next[0] = -1;
• nextval[4]，比较s[next[4]] ?= s[4]，next[4] = 1，s[1] = b，而s[4] = b，二者一致，则nextval[4] = next[1] = 0;
• nextval[5]，比较s[next[5]] ?= s[5]，next[5] = 2，s[2] = c，而s[5] = a，二者不一致，则nextval[5] = next[5] = 2；
• nextval[6]，比较s[next[6]] ?= s[6]，next[6] = 1，s[1] = b，而s[6] = a，二者不一致，则nextval[6] = next[6] = 1；
• 综上：nextval=[-1,0,0,-1,0,2,1];

详解

13、设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：(B)
A. 9
B. 10
C. 12
D. 15

解析：

1. 求next数组，next={-1,0,0,1,1,2};

2. 开始匹配

   • abaabaabcabaabc
     abaabc
     当比较到s[5]时，不成功，比较6次；

   • abaabaabcabaabc
     -----abaabc
     根据next[5]=2，移动S到S[2]处，从S[2]处开始比较，比较4次，成功；

   3. 一共比较10次；

三、填空题

1、对于模式串“abaabaab”，试给出其 lps 数组和 next 数组的值。其中 lps 是最长公共前缀后缀（longest prefix suffix）。数据间以一个空格分隔，最后一个数后面没有空格。
lps 数组： (0 0 1 2 3 4 5)
next 数组： (-1 0 0 1 2 3 4)

2、设目标串 text=“abccdcdccbaa”，模式串 pattern=“cdcc”，若采用 BF（Brute Force）算法，则在第 (6)趟匹配成功。

3、若 n 为主串长度，m 为模式串长度，采用 BF（Brute Force）模式匹配算法，在最好情况下需要的字符比较次数为 (m)。

4、n 为主串长度，m 为模式串长度，采用 BF（Brute Force）模式匹配算法，在最坏情况下需要的字符比较次数为 ((n-m+1)m)。

四、函数题

1、插入子串

请编写函数，在目的串中插入源串。
函数原型

// 插入子串
char* StrInsert(char *dst, int index, const char *src);
1
2

说明：dst 为指示目的串起始地址的指针，index 为插入位置(下标)，src 为指示源串起始地址的指针。函数在目的串 dst 下标 index 处插入源串 src，函数值为 dst。
要求：函数能容错运行。若 index 不正确，则不插入子串。
裁判程序

#include <stdio.h>

// 插入子串
char* StrInsert(char *dst, int index, const char *src);

int main()
{
    char a[65536], b[65536];
    int i;
    gets(a);
    scanf("%d%*c", &i);
    gets(b);
    StrInsert(a, i, b);
    puts(a);
    return 0;
}

/* 你提交的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入样例1

abcd
2
ef
1
2
3

输出样例1

abefcd
1

输入样例2

abcd
4
ef
1
2
3

输出样例2

abcdef
1

输入样例3

abcd
10
ef
1
2
3

输出样例3

abcd
1

实现代码：

char* StrInsert(char *dst, int index, const char *src){
	if(index>strlen(dst))
	 return dst;
	char str[65536];
	return strcat(strcpy(dst + index,src),strcpy(str,dst+index));
}
1
2
3
4
5
6

2、替换子串

请编写函数，替换子串。
函数原型

// 替换子串
char* StrStuff(char *dst, int idx, int len, const char *src);
1
2

说明：dst 为指示目的串起始地址的指针，idx 为待删除子串的起始位置(下标)，len 为待删除子串的长度，src 为指示待插入源串的起始地址的指针。函数将目的串 dst 中从下标 idx 处开始、长度为 len 的子串替换为源串 src，函数值为 dst。
要求：函数能容错运行。若 len 不正确，则自动修正。若 idx 不正确，则不作任何处理。
裁判程序

#include <stdio.h>

// 替换子串
char* StrStuff(char *dst, int idx, int len, const char *src);

int main()
{
    char a[1024], b[1024];
    int i, n;
    gets(a);
    scanf("%d%d%*c", &i, &n);
    gets(b);
    StrStuff(a, i, n, b);
    puts(a);
    return 0;
}

/* 你提交的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入样例1

abcd
1 2
efg
1
2
3

输出样例1

aefgd
1

输入样例2

abcd
1 5 (注：按3处理)
efgh
1
2
3

输出样例2

aefgh
1

输入样例3

abcd
2 -5 (注：按0处理)
efg
1
2
3

输出样例3

abefgcd
1

输入样例4

abcd
8 3
efg
1
2
3

输出样例4

abcd
1

实现代码：

char* StrInsert(char *dst, int index, const char *src){
	if(index>strlen(dst))
	 return dst;
	char str[65536];
	strcpy(str,dst+index);
    strcpy(dst + index,src);
	return strcat(dst,str);
}
char* StrStuff(char *dst, int idx, int len, const char *src){
	char str[1024];
	int slen=strlen(dst);
	if(idx>slen||idx<0)
     	return dst;
	if(len>slen-idx)
		len=slen-idx;
	if(len<=0)
		return StrInsert(dst,idx,src);	
	strcpy(dst+idx,dst+idx+len); 
	return StrInsert(dst,idx,src);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

下一节：算法与数据结构复习 第五章 树及二叉树(详解)