给定一个模式串T = 'abcabx',其next数组为 next[1] = 0, next[2] = 1, next[3] = 1, next[4] = 2, next[5] = 3, next[6] = 0。若使用KMP算法进行字符串匹配,在主串S='abcaabcaabcabx'中进行模式串匹配过程中,当匹配到主串的第7个位置字符 'a' 与模式串的第6个位置字符 'x' 失配后,下一步模式串需要从哪个位置开始与主串的第7个位置重新比较?

答案解析

核心考点说明:KMP算法中next数组的运用。 解题思路分析:当模式串T的第j个位置与主串S的第i个位置失配时,模式串T下一步需要从第next[j]个位置开始与S[i]重新比较。 已知next数组为 next[1] = 0, next[2] = 1, next[3] = 1, next[4] = 2, next[5] = 3, next[6] = 0。 当T的第6个位置'x'与S的第7个位置'a'失配时,下一个比较位置取决于next[6]的值,即0。 由于题目约定next数组的下标从1开始,所以应该从模式串T的第1个位置重新开始比较。 选项分析: - A. 正确。next[6] = 0,表示模式串需要从第1个位置开始。 - B. 错误。next[6]不等于1。 - C. 错误。next[6]不等于2。 - D. 错误。next[6]不等于3。 易错点提醒:注意next数组的索引从1开始,当next[j]=0时,表示从模式串的第一个字符开始比较。理解next数组是理解KMP算法的关键。
正确答案:A
随机推荐
开始刷题