我目前正在学习模式匹配算法,并遇到了这两种算法。我有以下大体的想法:将文本与失败数组进行比较以移位字符串O(m),其中m是模式的长度,以计算失败数组花费O(m),花费O(n),time to intelligentlytakes a
黑石所以我相信答案是正确的,因为假设每次你对不同的文本运行算法时,预处理只有O(n),而对于BM,它是O(n +字母表的大小)。然而,我不确定我是否做了正确的假设,即每次重新运行算法时都会重新计算一个新表。因为说文本总是落在英语的字母表中。我只需要计算表一次,然后重