我想我理解 Fischer & Paterson 算法与此处显示的“无关”模式匹配：http: //u.cs.biu.ac.il/~amir/AlgII/fp-set1.html
但是，据我了解，可以使用“不关心”一维匹配来解决 O((n^2)(logm)) 时间内的二维匹配。为此，应该在每个字符串的末尾或类似的东西后面附加一个“不关心”符号，并将其转换为一维问题。那是我不太明白的部分。我做了一些尝试，但我看不出这有什么帮助。
那么，带有“不关心”的一维匹配如何帮助解决二维匹配？
谢谢。
编辑：我想我有点明白了。文本需要线性化（其行的串联）。模式也是如此，但在每一行之后，应该添加 nm 无关符号（模式的最后一行除外）。然而，我认为这需要 O((n^2)(log(m^2))) 时间，我认为前面提到的时间是不可能的。评论？