algorithm - 一种输出敏感模式匹配算法

Question

这是面试第3步问我的模式匹配问题(我想可能是KMP的输出敏感版本，不确定。也解决不了问题)。

和往常一样，我们有一个文本 T，但这次它由来自 t_1,...,t_2k 的字符组成，而 P 是来自 p1,...,pk 的模式。

它们都来自相同的字母表，其符号来自 1,...,k。但并非所有符号都需要出现在文本或图案中。

如果我们知道没有字母符号在模式 P 中出现超过 n 次，找到一个 O(kn) 算法来构造一个长度为 k + 1 的向量 C，其中 C[i] 是 P 出现的位置数同意 ti...ti+k−1。

有什么想法吗？

Answer 1

这要简单得多 - 看看复杂度 - O(kn) - 这意味着蛮力:

要计算 C[i]，只需同时遍历从位置 0 开始的模式和从位置 i 开始的文本并计算匹配项。还行吧)。因此计算整个 C 需要 n 倍的时间，所以 O(nk)。