如何用模式匹配解决二维匹配问题并不在意？

Question

我想我明白费&帕特森算法模式相匹配的“无关”如下图所示： http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html

不过，我的理解是，可以使用“不关心”一维匹配来解决O（（n^2）（logm））时间内的二维匹配。为此，应该在每个字符串的末尾添加一个“不关心”符号，或者将其转换为一维问题。这是我不了解的部分。我做了一些尝试，但我看不出有什么帮助。

那么，与“不关心”的1D匹配如何帮助解决2D匹配？

谢谢。

编辑：我想我有点得到它。文本需要线性化（连续的行）。模式也是一样，但在每行之后，应添加n-m无关符号（除了模式的最后一行）。然而，我认为这会得到O（（n^2）（log（m^2）））时间，我认为前面提到的时间是不可能的。注释？

Answer 1

请注意，因为您的时间范围实际上相当于O（日志m），所以您的时间限制为0。