algorithm - 字符串 A 中有多少个不包含字符串 B 作为子字符串的不同子字符串

Question

如何使用 KMP 算法查找不包含字符串 B 作为子字符串的字符串 A 的不同子字符串的数量？

我使用 KMP 算法解决了另一个问题，但找不到如何用 KMP 解决这个问题。

提前致谢。

Answer 1

我认为 KMP 是计数问题中的简单部分，你需要一个非常清晰的头脑。使用 KMP，您可以依次遍历 A 的字符，并检测 A 中结束出现 B 的字符。您可以使用它来计算 A 中包含 B 的子串的数量。

如果 A 的一个字符结束了 B 的出现，那么每个以该结尾的子字符串开始足够远以包含 B 实际上包含 B。太短而不能包含 B 的子字符串显然不包含。因此，在这种情况下，您可以计算以包含 B 的字符结尾的 A 子串的数量。

如果 A 的字符没有结束 B 的出现，那么每个以该结尾的子字符串开始足够远以包含先前出现的 B 实际上包含 B。因此（假设您记得 B 最后一次出现的位置）您可以再次计算在此位置结束的包含 B 的子字符串的数量。

所以（在时间上与 A 的长度加上 B 的长度成线性关系，因为计算在每个位置结束的子串的数量只是做一些简单的算术）你可以计算 A 的包含 B 的子串的数量。当然，你想要不包含 B 的子串的数量，但 A 的子串总数只是 A 长度的二次方，所以这也很容易。