c++ - 在 C/C++ 中查找字符串中具有任意字符顺序的子字符串

Question

假设我有一个字符串“abcdpqrs”，现在“dcb”可以算作上述字符串的子字符串，因为字符在一起。“pdq”也是上述字符串的一部分。但是“bcpq”不是。我希望你得到我想要的。有什么有效的方法可以做到这一点。我所能想到的就是借助哈希来做到这一点。但即使在 O(n) 程序中也需要很长时间，因为在许多情况下需要回溯。任何帮助将不胜感激。

Answer 1

这是一个 O(n * alphabet size) 的解决方案:

让我们维护一个数组 count[a] = 字符 a 在当前窗口出现了多少次 [pos; pos + 子串的长度 - 1]。窗口向右移动1(count[s[pos]]--, count[s[pos + substring lenght]]++, pos++)可以在O(1)时间内重新计算。现在我们需要的是检查每个 pos 的计数数组是否与子字符串的计数数组相同(它只能计算一次)。

其实可以改进为O(n + alphabet size):

我们可以维护数字 diff = 与当前窗口的子字符串中的计数值不相同的字符数，而不是以天真的方式比较计数数组。关键的观察是 diff 以明显的方式发生变化，我们应用 count[c]-- 或 count[c]++(它要么增加，减少，要么保持不变，仅取决于 count[c] 值)。当且仅当当前位置的 diff 为零时，两个计数数组才相同。