如何用不关心的模式匹配来解决二维匹配问题？
我想我理解费舍尔和用于与“不关心”进行模式匹配的帕特森算法如下所示： http://u.cs.biu.ac.il/ ~amir/AlgII/fp-set1.html
但是，据我了解，可以使用“不关心”一维匹配来解决 O((n^2) 中的二维匹配（对数）） 时间。为此，应在每个字符串的末尾附加一个“不关心”符号或类似的符号，并将其转换为一维问题。这是我不太明白的部分。我已经做了一些尝试，但我看不出这有什么帮助。
那么，“不关心”的一维匹配如何帮助解决二维匹配呢？
谢谢。
编辑：我想我有点明白了。文本需要线性化（行的串联）。模式也是如此，但在每行之后，应添加 nm 无关符号（模式的最后一行除外）。然而，我认为这需要 O((n^2)(log(m^2))) 时间，并且我认为前面提到的时间是不可能的。评论？
I think I understand the Fischer & Paterson algorithm for pattern matching with "don't cares" shown here:
http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html
However, as I understood it is possible to use the "don't cares" one-dimensional matching to solve the two-dimensional matching in O((n^2)(logm)) time. For that, a "don't care" symbol should be appened to the end of each string or something like that and converting this to a one-dimensional problem. That's the part I don't really understand. I've made a few attempts but I can't see how that helps.
So, how does 1D-matching with "don't cares" helps solve 2D-matching?
Thanks.
EDIT: I think I sort of get it. The text needs to be linearized (concatenation of its rows). Same goes for the pattern but after each row, n-m don't-care symbols should be added (except for the last row of the pattern). Yet, I think this gets O((n^2)(log(m^2))) time and I think the previously mentioned time is not possible. Comments?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
请注意，log m2 = 2 log m，因此您的时间限制实际上相当于 O(n2 log m)。
Note that log m2 = 2 log m, so your time bound in fact is equivalent to O(n2 log m).