( EDITED )
Предположим, у вас есть матрица A размера n x m и матрица B размеров k x l, проблема поиска вхождений B в A имеет простую сложную временную сложность O(n m k l) с требованием O(1) памяти.
В общем, вы можете легко доказать, что вы не можете быть лучше, чем O(n m), рассматривая случай k = l = 1, который требует проверки всех элементов содержащей матрицы, поэтому O(n m). Это та же самая причина, по которой алгоритмы строки поиска не могут быть (глобально) суперлинейными.
Я предполагаю, что ваше требование быть O(N) более точно соответствует требованию быть O(n m). Если бы это было возможно, вы могли бы предположить, что подобный алгоритм может быть адаптирован к задаче поиска строки со сложностью O(n) (n - размер ввода), независимо от размера шаблона k. Такой алгоритм не был найден (и, вероятно, даже существует). По этой причине я склонен полагать, что то, что вы ищете, в настоящее время, по возможности, находится за пределами человеческого знания.
Вместо этого, на основе алгоритмов поиска строк литературы то, к чему вы могли бы стремиться, - это достичь сложности O(n m + k l).
Возможным подходом было бы адаптировать один из вышеупомянутых алгоритмов поиска строки к этой проблеме, и, следовательно, вы должны быть в состоянии получить аналогичные временные сложности и требования к памяти.
Например, ваш алгоритм и @ PaulHankin answer являются описанием адаптации алгоритма Рабина-Карпа к 2D корпусу. В то время как ваша версия использует действительно плохой ха sh (первый элемент каждой матрицы), если бы вы рассчитывали более сложный / подходящий га sh (как предложено, но не предоставлено - по крайней мере, на момент написания статьи) в @ PaulHankin ответ ), как скользящий га sh, тогда вы сможете пропустить две самые внутренние петли большую часть времени, в то время как вращающийся ха sh будет убедитесь, что вы не добавляете в алгоритм дополнительную сложность, зависящую от размера ввода, что приведет к O(n m + k l) сложности времени (O(k l) получается из вычисления ha sh на B) и O(1) памяти требование.
Адаптация других алгоритмов поиска строк (например, алгоритм Кнута-Морриса-Пратта (KMP) или Двусторонний алгоритм поиска строк (2WSS) ) может потребоваться некоторая «линеаризация» алгоритма (а не только постановка задачи), что будет означать использование модуля arithmeti c для определения правильных смещений при любых обстоятельствах, что может быть утомительным, но я не вижу причины, по которой это было бы невозможно или привело бы к потере ожидаемых сложностей.
Другой вариант - адаптировать алгоритмы поиска строк для работы с чередованием в каждом измерении. Но опять же, это может оказаться таким же сложным, как и работа с какой-то «линеаризованной» проблемой.
Последнее сообщение здесь заключается в том, что определенно возможно go выйти за пределы O(n m k l) и в конечном итоге O(n m + k l), но это не так. легко.