给定主串 S = 'ababcabcacbab' 和模式串 T = 'abcac',使用 BF (Brute-Force) 算法进行模式匹配。当主串的索引 i = 7,模式串的索引 j = 3 时,下一步操作会发生什么?

答案解析

核心考点说明:本题考察 BF 算法(暴力匹配算法)的核心逻辑,特别是匹配失败时 i 和 j 指针的回溯机制。解题思路分析:在 BF 算法中,如果主串和模式串的当前字符匹配成功,则 i 和 j 同时递增;如果匹配失败,则 j 回溯到模式串的起始位置 1,而 i 回溯到本次匹配开始位置的下一个位置。具体步骤如下: 1. 当 i=7, j=3时,S[7]='c', T[3]='c',匹配成功,i 和 j 分别递增到 8 和 4。 2. 当 i=8, j=4时,S[8]='a', T[4]='a',匹配成功,i 和 j 分别递增到 9 和 5。 3. 当 i=9, j=5时,S[9]='c', T[5]='c',匹配成功,i 和 j 分别递增到 10 和 6。由于 j 达到了T的长度,匹配完成。 如果匹配过程中某个位置匹配失败,如,如果 i=6,j=1时,S[6]='b',T[1]='a',匹配失败。 当 i=7, j=3 时,发生匹配时,并没有失败,所以不会发生回溯。而是继续进行匹配。此时,i变为8,j变为4. 每个选项的详细分析: A. 错误, 匹配没有失败,不需要回溯,j不会回溯到1,i也不会回溯到2,因此不正确。 B. 正确答案。当i=7, j=3 时, S[7]='c',T[3]='c'匹配,此时i++,j++,即i=8,j=4。选项中j回溯到1是错误的。 C. 错误,匹配没有失败,不需要回溯,j不会回溯到1, 匹配成功后, j 会递增到 4, i 会递增到 8,但 j 不是回溯到1 D. 错误, 匹配没有失败,不需要回溯,j不会保持不变。而是继续递增到4。所以不正确。 易错点提醒: 容易混淆匹配成功和失败时的处理方式。匹配成功时,i 和 j 都递增;只有匹配失败时,j 才回溯到 1,i 回溯到当前匹配起始位置的下一个位置。
正确答案:B
随机推荐
开始刷题