Есть ли какие-либо бумаги или объяснения о том, как реализовать двумерный KMP?

Question

Я попытался решить проблему двумерного поиска, используя комбинацию Aho-Corasick и одномерного KMP, однако мне все еще нужно что-то более быстрое.

Чтобы уточнить, у меня есть матрица символовразмером n1 * n2, и я хочу найти все вхождения меньшей матрицы B размером m1 * m2, и я хочу, чтобы это было в O (n1 * n2 + m1 * m2), если это возможно.

Например,:

A = a b c b c b
    b c a c a c
    d a b a b a
    q a s d q a

и

B = b c b
    c a c
    a b a

алгоритм должен возвращать индексы, скажем, левого верхнего угла совпадения, которые в этом случае должны возвращать (0,1) и (0,3).обратите внимание, что случаи могут перекрываться.

Answer 1

Существует алгоритм, который называется Алгоритм Бейкера-Берда , с которым я недавно столкнулся, и который является частичным обобщением KMP в двух измерениях. Он использует два алгоритма в качестве подпрограмм - алгоритм Aho-Corasick (который сам по себе является обобщением KMP) и алгоритм KMP - для эффективного поиска шаблона в двумерной сетке.

Я не уверен, что это то, что вы ищете, но, надеюсь, это поможет!