c++ - 给定一个单词和一段文本，我们需要返回出现的字谜

Question

给定一个单词和一段文本，返回文本中该单词的字谜出现次数。例如。单词是“for”，文本是“forxxorfxdofr”，“for”的变位词将是“ofr”、“orf”、“fro”等。所以这个特定示例的答案是 3。

我有蛮力方法，它获取单词的所有排列，然后比较文本是否包含它，并增加出现次数，但这是 O(N^2) 方法。我正在寻找更好的复杂性。

Answer 1

您可以简单地查找字符数。

例如，您正在寻找look 的变位词。所以，您正在寻找:

• 一个 4 个字符长度的单词，
• 1 l、2 o 和 1 k。

简单处理前 4 个字母，存储计数。检查您是否有匹配项。添加下一个字符(递增)，删除旧字符(递减)。再检查一遍。等等……