给定一个字符串S = "ababaabab", 使用BF算法(暴力匹配算法)查找模式串 T = "ababaa" 在 S 中第一次出现的位置,下列描述正确的是(下标从0开始):
答案解析
核心考点说明:本题考察BF(Brute Force)算法,即暴力匹配算法的执行过程,需要理解算法中主串和模式串指针如何移动,以及发生回溯的条件。
解题思路分析:BF算法是逐个字符匹配主串和模式串,当模式串的字符匹配失败时,主串指针回溯到上一轮起始匹配的后一个位置,模式串指针回到起始位置。
选项分析:
* A:错误。 匹配过程中,当 S[0...4]="ababa" 和 T[0...4]="ababa"匹配成功后,S[5]='b' 和T[5]='a'匹配失败,第一次回溯,主串指针i回溯到1, 模式串指针j回溯到0;当S[1...5] 和 T 不匹配, 主串指针 i 回溯到2,模式串指针j回到0。 当S[2...7]=“abaaba”与T匹配,在第2个位置匹配成功。 因此共发生了2次回溯。 第一次匹配成功的位置在2.
* B:正确。如上分析,共发生2次回溯,第一次匹配的位置在下标2处。
* C:错误。 匹配过程回溯了2次。
* D:错误。 匹配过程回溯了2次,并且第一次匹配的位置在下标2处。
易错点提醒:BF算法的特点是当匹配失败时主串指针和模式串指针都需要回溯,理解回溯的意义和位置是关键。
正确答案的关键依据:BF算法的匹配过程,包括主串和模式串指针的移动和回溯。
正确答案:B