跳到主要内容

408模拟选择题 · 数据结构 · 第4章 串

4.2 串的模式匹配​

4.2.2 串的模式匹配算法——KMP算法​

  1. 【王道·卷六-Q04】 在使用KMP算法进行模式匹配的过程中，如果某趟匹配失败，i指示主串中失配的位置，j指示模式串中失配的位置，若 k=next[j],k′=next[i]\displaystyle k = next[j], k^{\prime} = next[i]，则下一趟匹配比较时，模式串的第（ ）位与主串中的第i位对齐。
A. j+1\displaystyle j + 1    B. k\displaystyle k    C. k′\displaystyle k^{\prime}    D. j−1\displaystyle j - 1
查看答案与解析

答案： B

解析： KMP 算法发生失配时，主串指针 i\displaystyle i 不回退，模式串指针由 j\displaystyle j 调整为

j=next[j]=k\displaystyle j=next[j]=k

因此下一趟比较时，模式串的第 k\displaystyle k 位与主串中当前失配位置的第 i\displaystyle i 位对齐，选择 B。

next\displaystyle next 数组是根据模式串自身的前缀和后缀关系得到的，与主串下标 i\displaystyle i 无关，所以 next[i]\displaystyle next[i] 在这里没有意义；A、D 也不能利用已经匹配成功的前后缀信息。

  1. 【王道·卷七-Q04】 串'acaba'的next数组值为（ ）。
A. 01234    B. 01212    C. 01121    D. 01230
查看答案与解析

答案： C

解析： 采用题目所用的 1 起始下标约定，令 next[1]=0\displaystyle next[1]=0，并根据当前位置之前子串的最长相等真前缀和真后缀确定其余值。

  • next[1]=0\displaystyle next[1]=0；
  • next[2]=1\displaystyle next[2]=1，这是约定的初始值；
  • 求 next[3]\displaystyle next[3] 时考查子串 ac，不存在非空的相等真前缀和真后缀，因此为 1；
  • 求 next[4]\displaystyle next[4] 时考查子串 aca，最长相等真前缀和真后缀均为 a，长度为 1，因此 next[4]=2\displaystyle next[4]=2；
  • 求 next[5]\displaystyle next[5] 时考查子串 acab，不存在非空的相等真前缀和真后缀，因此为 1。

所以 next 数组为

0,1,1,2,1\displaystyle 0,1,1,2,1

即 01121，选择 C。

4.2.3 KMP算法的进一步优化​

  1. 【王道·卷八-Q04】 已知字符串 S\displaystyle S 为"aabaabcabc"，模式串 T\displaystyle T 为"aaabc"。使用nextval优化后的KMP算法进行匹配，匹配到 i=2\displaystyle i = 2 且 j=2\displaystyle j = 2 时，失配 (S[i]≠T[j])\displaystyle (S[i]\neq T[j])。则下次开始匹配时，i和 j\displaystyle j 分别是（ ）。
A. 2和2    B. 2和1    C. 3和0    D. 3和2
查看答案与解析

答案： C

解析： 模式串 T="aaabc"\displaystyle T=\text{"aaabc"} 的前 3 个字符均为 a。当 i=2,j=2\displaystyle i=2,j=2 时，主串字符为 b，模式串字符为 a，发生失配。若按普通 next 数组逐级回退，还会重复拿同一个主串字符 b 与前面的 a 比较；nextval 的作用正是跳过这种必然再次失配的比较。

对该位置有

nextval[2]=−1\displaystyle nextval[2]=-1

失配后先令 j=−1\displaystyle j=-1，随后按照 KMP 主循环的规则，在 j=−1\displaystyle j=-1 时同时执行 i++\displaystyle i++ 和 j++\displaystyle j++，于是下一次真正开始字符比较时

i=3,j=0\displaystyle i=3,\qquad j=0

因此选择 C。

  1. 【竟成·模拟一-08】 已知模式串为"ababac"，主串为"cbabababac"。在KMP算法匹配过程中，第一次出现"失配"时，i=j=0。则下列描述正确的是（）。
A. 当主串第1个字符'c'与模式串第1个字符'a'发生失配时，模式串指针应移动到next[0]的位置，主串指针不变
B. 模式串"ababac"的nextval数组为[-1,0,0,1,2,3]
C. 当主串第8个字符'b'与模式串第6个字符'c'失配后，下次开始匹配时，主串指针i=7，模式串指针j=-1
D. 整个匹配过程中，字符比较的总次数为11次
查看答案与解析

答案： D

解析： 模式串 ababac 的普通 next 数组为 [-1,0,0,1,2,3]，而优化后的 nextval 数组为

[−1,0,−1,0,−1,3]\displaystyle [-1,0,-1,0,-1,3]

因此 B 把普通 next 数组误当成了 nextval 数组。

按 nextval 进行匹配并统计字符比较次数：

  1. 主串第 1 个字符 c 与模式串第 1 个字符 a 比较，失配，累计 1 次；随后有效状态变为 i=1,j=0\displaystyle i=1,j=0。
  2. 主串第 2 个字符 b 与模式串第 1 个字符 a 比较，失配，累计 2 次；随后变为 i=2,j=0\displaystyle i=2,j=0。
  3. 主串第 3～7 个字符 ababa 与模式串前 5 个字符 ababa 依次匹配，共增加 5 次，累计 7 次。
  4. 主串第 8 个字符 b 与模式串第 6 个字符 c 失配，累计 8 次。此时 j=nextval[5]=3\displaystyle j=nextval[5]=3，而不是 −1\displaystyle -1，所以 C 错误。
  5. 保持主串指针不变，主串第 8 个字符 b 再与模式串第 4 个字符 b 比较，随后第 9 个字符 a、第 10 个字符 c 继续匹配，共增加 3 次。

因而总比较次数为

8+3=11\displaystyle 8+3=11

D 正确。A 只描述了将 j\displaystyle j 暂时置为 next[0]=−1\displaystyle next[0]=-1 的中间状态；下一次真正进行字符比较前，算法还会令主串指针前移并将 j\displaystyle j 恢复为 0，因此不能说主串指针始终不变。

  1. 【竟成·模拟六-03】 已知字符串S为"abaacaadaafa"，模式串P为"aada"。采用KMP算法结合nextval数组进行匹配，匹配成功时共进行（）次比较。
A. 11    B. 12    C. 13    D. 14
查看答案与解析

答案： B

解析： 模式串为 aada。采用从 1 开始编号的 KMP 约定，其 nextval 数组为

nextval=[0,0,2,0]\displaystyle nextval=[0,0,2,0]

按题目所采用的算法判定口径，匹配过程如下：

  1. 主串第 1 个字符 a 与模式串第 1 个字符 a 匹配。
  2. 主串第 2 个字符 b 与模式串第 2 个字符 a 失配，模式串指针回退到 0；随后主串指针前移。
  3. 从主串第 3 个字符开始，a、a 分别与模式串前两个 a 匹配。
  4. 主串第 5 个字符 c 与模式串第 3 个字符 d 失配，模式串指针退到第 2 个字符；c 再与 a 失配，模式串指针再次退到 0，随后主串指针前移。
  5. 从主串第 6 个字符开始，子串 aada 与模式串完整匹配。

整个过程中，按 KMP 主循环中的比较判定次数统计，共进行 12 次比较，因此选择 B。nextval 的作用是跳过模式串中必然会再次失配的位置，避免无意义的重复回退。