algorithm - 如何用don't cares 模式匹配解决二维匹配问题？

Question

我想我理解 Fischer & Paterson 算法与此处显示的“无关”模式匹配: http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html

但是，据我了解，可以使用“无关紧要”的一维匹配来解决 O((n^2)(logm)) 时间内的二维匹配。为此，应该在每个字符串的末尾附加一个“无关”符号或类似的东西，并将其转换为一维问题。那是我不太明白的部分。我做了几次尝试，但看不出有什么帮助。

那么，“不关心”的一维匹配如何帮助解决二维匹配问题？

谢谢。

编辑:我想我有点明白了。文本需要线性化(连接其行)。模式也是如此，但在每一行之后，应添加 n-m 个无关符号(模式的最后一行除外)。然而，我认为这需要 O((n^2)(log(m^2))) 时间，我认为前面提到的时间是不可能的。评论？

Answer 1

请注意 log m² = 2 log m，因此您的时间限制实际上相当于 O(n² log m)。