Мне кажется, я понимаю алгоритм Фишера и Патерсона для сопоставления с шаблоном, который показан здесь: "все равно":
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))) время, и я думаю, что упомянутое ранее время невозможно. Комментарии?