知识点

1.基本概念

• 串的定义
  • 串是由0个或多个字符组成的有限序列，又叫字符串。
• 空串
  • 长度为0的串，不包含任何字符。
• 空白串
  • 由一个或多个空白字符组成的串。
• 子串
  • 串的任意个连续字符组成的串子序列。子串的位置是以子串在主串中首次出现时的第一个字符在主串中的位置来表示。
• 主串
  • 包含子串的串相应的叫主串。
• 字符数为n的串:
  • 子串的个数为：n(n+1)/2+1
  • 真子串的个数为：n(n+1)/2

2.串的模式匹配

主串：S=a b a b c a b c a c b a b

模式串：T = a b c a c

BF算法（Brute-Force）

平均时间复杂度O(n×m)

KMP算法

平均时间复杂度O(m+n)

串的模式匹配：

• BF算法：
  • 匹配失败：
    • 主串i回溯到i-j+2
    • 模式串j回溯到j=1
• KMP算法：
  • 匹配失败：
    • 主串i不回溯
    • 模式串j回溯仅与模式串有关，j的下一个回溯地址与next[j]有关
    • j=0时，i=i+1

3.next[j]与nextval[j]的计算

next[j] 的计算方式

步骤：（前提j的初始值为1，初始值为0则所有值减1）

1. 第1个是0，第2个是1
2. max{n个前缀=n个后缀}，写n+1
3. 前缀≠后缀，写1

注意：串：a b c d –> 前缀：a、ab、abc;后缀：d、cd、bcd。

nextval[j]的计算方式

步骤：（前提j的初始值为1，初始值为0则所有值减1）

1. 第一位写0
2. 第2位若与第1位相同为0，不同为1
3. 从第3位开始根据next[j]值指路
   • 相同：=对方的nextval的值
   • 不同：=当前的next的值

4.串的存储结构

顺序存储

链式存储

练习题

一、 单选题

1.题目：下面关于串的叙述中，（ ）是不正确的？
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储

2.题目：串的长度是指（ ）。
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含相同字符的个数
D. 串中所含非空格字符的个数

3.题目：串是一种特殊的线性表，其特殊性体现在（ ）。
A. 可以顺序存储
B. 数据元素是字符
C. 可以链式存储
D. 数据元素没限制

4.题目：下面关于串的叙述中，正确的是( )。
A. 串是一种特殊的线性表
B. 串中元素只能是字母
C. 空串就是空格串
D. 串的长度必须大于零

5.题目：两个字符串相等的条件是( )。
A. 串的长度相等
B. 含有相同的字符集
C. 都是非空串
D. 两个串的长度相等且对应位置的字符相同

6.题目：若串str=“Software”，其子串的个数是( )。
A. 8
B. 9
C. 36
D. 37

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

8.题目：空串的长度是（ ）。
A. 0
B. 1
C. 2
D. 错误

9.题目：空串与空格串（ ）。
A. 相同
B. 不相同
C. 可能相同
D. 无法确定

10.题目：一个子串在包含它的主串中位置是指( )。
A. 子串的最后那个字符在主串中的位置
B. 子串的最后那个字符在主串中首次出现的位置
C. 子串的第一个字符在主串中的位置
D. 子串的第一个字符在主串中首次出现的位置

11.题目：与线性表相比，串的插入和删除操作的特点是( )。
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动元素更多

12.题目：在串的简单模式匹配中(BF)，当模式串位 j 与目标串位 i 比较时，两字符不相等，则 i 的位移方式是( )。
A. i++
B. i=j+1
C. i=i-j+1
D. i=j-i+1

13.题目：在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位 j 与目标串位 i 比较时，两字符不相等，则 i 的位移方式是( )。
A. i=next[j]
B. i不变或者移动到下一位置
C. j不变
D. j=next[j]

14.题目：在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位 j 与目标串位 i 比较时，两字符不相等，则 j 的位移方式是( )。
A. i=next[j]
B. i不变
C. j不变
D. j=next[j]

15.题目：已知字符串 s 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。采用KMP算法进行匹配，第一次出现“失配” (s[i] != t[j]) 时，i=j=5，则下次开始匹配时，i 和 j 的值分别是（ ）。
A. i=1, j=0
B. i=5, j=0
C. i=5, j=2
D. i=6, j=2

16.题目：对于KMP算法，在模式匹配时指示主串匹配位置的指针( )。
A. 不会变大
B. 不会变小
C. 都有可能
D. 无法判断

17.题目：设主串的长度为 n，子串的长度为 m，那么BF算法的时间复杂度为( )，KMP算法的时间复杂度为( )。
A. O(m) O(n)
B. O(n) O(m)
C. O(n×m) O(n+m)
D. O(n+m) O(n×m)

18.题目：设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称做（ ）。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长

19.题目：串“ababaaababaa”的next数组是（ ）。
A. -101234567888
B. -101010000101
C. -100123112345
D. 010101011

20.题目：串“ababaabab”的nextval数组是（ ）。
A. -10-10-130-10
B. -10-10-110-10
C. -10-110-1-1-100
D. 010101011

21.题目：已知字符串 s 为 "bcacaabaabcca"，模式串 t 为 "cabaabc"。采用KMP算法进行匹配，第一次出现“失配”(s[i] ≠ t[j])时，i=1，j=0，则下次开始匹配时，i 和 j 的值分别是（ ）
A. i=1, j=0
B. i=0, j=1
C. i=2, j=0
D. i=1, j=2

二、 填空题

1.题目：给定模式串“aaaaacacab”，计算出每个字符的next函数值为 （中间无空格） 。

2.题目：已知字符串 s 为 “ababbabbababa”，模式串 t 为 “abaabc”。
采用KMP算法进行匹配，第一次出现“失配”(s[i] ≠ t[j])时，i=3, j=3，则下次开始匹配时，i 和 j 的值分别是 （1） 和 （2）。 请给出模式串 "abaabc" 的 next 数组值（从 j=0 开始）：

j	0	1	2	3	4	5
模式串	a	b	a	a	b	c
next[j]

答案解析

一、单选题解析

1.B – 空串是零个字符的串，由空格字符组成的串称为“空格串”，二者不同。

2.B – 根据定义，串中字符的总数称为串的长度。

3.B – 串是数据元素为字符的线性表。

4.A – 串是特殊的线性表。空串≠空格串，串中元素不限于字母，长度可为零。

5.D – 字符串相等要求长度相等且每个对应位置的字符都相同。

6.D – 子串总数公式：n(n+1)/2+1（n=8时，8*9/2+1=37）。

7.B – 同第1题。

8.A – 空串不含字符，长度为0。

9.B – 空串（零字符）与空格串（含空格字符）本质不同。

10.D – 子串的位置定义为其首字符在主串中首次出现的位置。

11.A – 串的运算通常以整个串或较长子串为操作对象。

12.C – BF算法失配时，i回溯到本轮起始位置的下一个位置：i=i-j+1。

13.B – KMP算法中i不回溯，通常保持不变，仅当j=0时可能后移一位。

14.D – KMP算法失配时，j回溯到next[j]指示的位置。

15.C – KMP失配时i不变（=5），j回溯到next[5]（模式串“abaabc”的next[5]=2）。

16.B – KMP算法中，主串指针i只增大（向后移动）或保持不变，永不减小（不回溯）。

17.C – BF最坏为O(n×m)；KMP为O(m+n)（其中计算next为O(m)，匹配为O(n)）。

18.B – 此操作为模式匹配。

19.C – 根据next函数定义计算可得（通常首位为-1）。

20.A – 根据nextval规则（优化next）计算可得。

21.C

二、填空题解析

1. -1012340101
   – 根据next函数定义（此处首位为-1的版本），对模式串“aaaaacacab”逐位计算最长相等前后缀的长度+1得到结果。
2. (1) 3
   (2) 1
   (3) -1
   (4) 0
   (5) 0
   (6) 1
   (7) 1
   (8) 2