NOIP2026复赛字符串处理与KMP算法专项练习

NOIP2026复赛字符串处理与KMP算法专项练习一、单选题（共5题，每题4分，共20分）1.题目：在KMP算法中，若模式串`P`的长度为`m`，文本串`T`的长度为`n`，且`P`在`T`中匹配成功，则KMP算法在最坏情况下的比较次数为多少？A.`m+n`B.`mn`C.`m+n-1`D.`m(n-m)`2.题目：已知模式串`P="ABABCABAB"`，则其部分匹配表（部分匹配表）的第一位和第二位的值分别为多少？A.0,0B.1,0C.0,1D.1,13.题目：在KMP算法中，当文本串`T`和模式串`P`的长度分别为`n`和`m`时，若`T`中存在`P`的多个不重叠的子串，则KMP算法在查找所有匹配的过程中最多执行多少次“失配”操作？A.`n`B.`m`C.`n+m`D.`nm`4.题目：给定文本串`T="ABCABCDABCDABDE"`和模式串`P="ABCD"`，使用KMP算法进行匹配时，`P`在`T`中的第几次匹配过程中会发生“失配”？A.第一次B.第二次C.第三次D.第四次5.题目：KMP算法的核心优势在于什么？A.空间复杂度低B.时间复杂度低C.能够处理重叠的子串D.不需要预处理模式串二、填空题（共5题，每题4分，共20分）1.题目：若模式串`P="ACDEFAC"`，则其部分匹配表的第6位的值为________。2.题目：在KMP算法中，当文本串`T`的某个位置`i`与模式串`P`的某个位置`j`发生“失配”时，若`j>0`，则KMP算法会继续比较`T[i]`与`P[________]`。3.题目：若模式串`P`的长度为`m`，其部分匹配表的最后一个值为`k`，则`P`中至少包含________个不重叠的相同子串。4.题目：给定文本串`T="ABCDEFABCDEF"`和模式串`P="ABCDEF"`，使用KMP算法进行匹配时，`P`在`T`中的第________次匹配成功时，会跳过`T`的前`n-m+1`个字符。5.题目：KMP算法的部分匹配表的作用是记录模式串中前缀与后缀的________，以避免重复比较。三、简答题（共3题，每题6分，共18分）1.题目：简述KMP算法的部分匹配表（PartialMatchTable，PMT）的构造过程。2.题目：若模式串`P="ABCDABD"`，请手动计算其部分匹配表，并解释第5位的值是如何得到的。3.题目：在KMP算法中，当文本串`T`和模式串`P`的某个位置发生“失配”时，为什么需要回溯到部分匹配表的某个位置继续比较？四、编程题（共2题，每题10分，共20分）1.题目：编写一个函数，实现KMP算法的部分匹配表的构造。输入为模式串`P`，输出为部分匹配表。例如：输入：`P="ABABCABAB"`输出：`[0,0,1,2,3,0,1]`2.题目：编写一个函数，使用KMP算法在文本串`T`中查找模式串`P`的所有匹配位置。输入为`T`和`P`，输出为`P`在`T`中所有匹配的起始索引列表。例如：输入：`T="ABCABCDABCDABDE"`,`P="ABCD"`输出：`[0,7]`答案与解析一、单选题答案与解析1.答案：A解析：KMP算法通过部分匹配表避免重复比较，最坏情况下比较次数为`m+n`。具体而言，文本串`T`的每个字符最多被比较一次，模式串`P`的每个字符最多被比较一次。2.答案：C解析：部分匹配表记录的是模式串前缀与后缀的最长相同长度。-第一位：`"AB"`与`""`相同，值为`0`。-第二位：`"AB"`与`"A"`不相同，`"A"`与`""`相同，值为`1`。3.答案：C解析：若`T`中存在`m`个不重叠的子串，KMP算法需要逐个匹配，每个匹配过程可能发生`m`次“失配”（最坏情况）。因此总“失配”次数为`n+m`。4.答案：B解析：匹配过程如下：-第一次：`"ABCD"`与`"ABCABCDABCDABDE"`匹配成功，跳过`"ABCD"`。-第二次：`"ABCD"`与`"ABCDABDE"`匹配失败（`'A'`不匹配`'A'`）。因此第二次匹配时发生“失配”。5.答案：D解析：KMP算法的核心优势在于预处理模式串的部分匹配表，避免重复比较，时间复杂度为`O(m+n)`。二、填空题答案与解析1.答案：3解析：部分匹配表第6位的计算：-前缀：`"ACDEF"`-后缀：`"AC"`最长相同长度为`"AC"`，值为`3`。2.答案：P[j-lps[j]]解析：`lps[j]`表示模式串`P`的前`j`个字符的最长相同前后缀长度，回溯时比较`T[i]`与`P[j-lps[j]]`。3.答案：m-k+1解析：若部分匹配表最后一个值为`k`，则模式串至少有`k`个相同子串（如`"ABCD"`的`k=3`，包含`"AB"`,`"BC"`,`"CD"`）。4.答案：1解析：第一次匹配成功时，`P`匹配`T`的前`m`个字符，后续匹配会跳过已匹配部分。5.答案：最长相同前后缀解析：部分匹配表记录前缀与后缀的最长相同长度，用于指导回溯。三、简答题答案与解析1.部分匹配表的构造过程：-初始化：部分匹配表`lps`长度为`m`，`lps[0]=0`。-从`i=1`到`m`：-若`P[i]==P[lps[i-1]]`，则`lps[i]=lps[i-1]+1`，否则：-若`lps[i-1]>0`，则将`i`回溯到`lps[lps[i-1]-1]`，继续比较；-否则，`lps[i]=0`。2.部分匹配表计算示例：`P="ABCDABD"`：-`lps[0]=0`-`lps[1]=0`（`"A"`与`"A"`相同）-`lps[2]=0`（`"AB"`与`"A"`不相同）-`lps[3]=1`（`"ABC"`与`"A"`相同）-`lps[4]=2`（`"ABCD"`与`"AB"`相同）-`lps[5]=0`（`"ABCDAB"`与`"A"`不相同）-`lps[6]=1`（`"ABCDABD"`与`"AB"`相同）最终`lps=[0,0,0,1,2,0,1]`。第5位`lps[4]=2`表示`"AB"`是`"ABCD"`的前缀和后缀的最长相同子串。3.回溯的原因：当`T[i]`不匹配`P[j]`时，部分匹配表`lps[j]`记录了`P`前`j`个字符的最长相同前后缀长度。这意味着`P`的前`lps[j]`个字符可以与`T`的前`i`个字符的前`lps[j]`个字符相同，因此可以将`P`回溯到`lps[j]`位置，避免重复比较。四、编程题答案与解析1.部分匹配表构造函数：pythondefcompute_lps(P):m=len(P)lps=[0]mlength=0i=1whilei<m:ifP[i]==P[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlps2.KMP匹配函数：pythondefkmp_search(T,P):n=len(T)m=len(P)lps=compute_lps(P)i=0#T的索引j=0#P的索引result=[]whilei<n:ifP[j]==T[i]:i+=1j+=1ifj==m:result.append(i-j)j=lps[j-1]elifi<n