在主串T=”babbabbacbabbac”中，我们要寻找子

[单选题]

在主串T=”babbabbacbabbac”中，我们要寻找子串S=”babbac”，为了找到这个子串，我们采用了KMP算法，请问到匹配成功时为止总共进行了多少次单字符的比较？

查看答案及解析

mhz931

从babbabbacbabbac中用kmp算法找到babbac：

1）计算LPS（longest prefix suffix，即词中最长的同时作为前缀和后缀的短词的长度）

对于例子中的 babbac, LPS = [0, 0, 1, 1, 2, 0] (如LPS[1] = 0, 因为ba中没有LPS; LPS[4] = 2，因为babba中LPS为ba, LPS[0]预设为0）（这一段是不算在匹配的步骤中的）

2）开始计算：

babbabbacbabbac

babbac （第5位错误，从第LPS[5-1] = 2位继续匹配）

bbac（成功）

因此总共单字符对比次数为10。

发表于 2025-04-16 19:12:42 回复(0)

提交观点

问题信息

查找

难度：

1条回答 29收藏 274浏览

扫一扫，把题目装进口袋