这只是出于好奇。我正在浏览一篇比较各种字符串搜索算法的文章,发现它们都设计用于找到第一个匹配的子字符串。这让我想...如果我想要找到所有子字符串的出现呢?
我相信我可以创建一个循环,使用KMP或BM的变体,并将每个找到的出现转储到一个数组中,但这似乎并不是最快的方法。
分治算法难道不是更好的选择吗?
例如,假设您正在查找字符串“abc”在字符串“abbcacabbcabcacbccbabc”中的所有出现。
- 在第一次查找时,找到第一个字符的所有出现并存储它们的位置。
- 在每个附加通行证上,使用前一个通行证中的位置查找下一个字符的所有出现,每次迭代都减少下一个通行证的候选项。
考虑到我想出这个想法的轻松程度,我认为30年前已经有人提出了这个想法并进行了改进。