给定一个单词word
和一个字符串S
,找到S
中的所有起始索引——word
的回文。
例如,假设word
是“ab”,并且S
是“abxaba”,则返回0,3和4。
对于这个问题野蛮的解决方案是遍历S
中每个单词大小的窗口并检查它们是否是回文,如下所示:
这将花费O(|W| * |S|)时间。有没有更快的方法呢?
解决这个问题可以使用的一种方法是Rabin-Karp算法。基本思想是我们可以对目标word
做一个基于频率的散列,并检查s
下的任何窗口是否散列为相同的值。也就是说,散列将是每个字符和其频率的char * prime_num ** char_freq
之和。如果word
和窗口的散列匹配,则我们可以对两个字符串手动加上==
。因为预计冲突很少,所以时间将是O(S)。但是,解决这个问题有一个更简单的方法:
请注意,沿着窗口移动意味着当实际只有一小部分更新的时候,重新计算整个窗口的频率计数。这种见解引导我们采取以下策略:
我们通过增加窗口中的新字符并删除旧的字符来区分我们的频率字典。
这应该在O(S)时间运行。
欢迎继续探索其他有趣的编程问题。