在主串T=”babbabbacbabbac”中，我们要寻找子串S=”babbac”，为了找到这个子串，我们采用了KMP算法，请问到匹配成功时为止总共 进行了多少次单字符的比较？
区块链毕设网qklbishe.com为您提供问题的解答
在主串T=”babbabbacbabbac”中，我们要寻找子串S=”babbac”，为了找到这个子串，我们采用了KMP算法，请问到匹配成功时为止总共进行了多少次单字符的比较？
从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。
12:42
以上就是关于问题在主串T=”babbabbacbabbac”中，我们要寻找子串S=”babbac”，为了找到这个子串，我们采用了KMP算法，请问到匹配成功时为止总共 进行了多少次单字符的比较？的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}