Передо мной стоит достаточно тривиальная задача: найти все вхождения подмассива в массив. Стандартным методом (на каждой итерации по элементам первоначального массива берём K элементов и сравниваем полученный массив значений с искомым подмассивом длиной K) поиск вхождений в худшем случае занимает O((N-K+1)*K), что приемлемо на небольших входных данных.
Но обработать, увы, таким образом мне предстоит данные внушительные. Я подумал над тем, чтобы реализовать поиск вхождений за О(N), т.е. каким-то образом сохраняя данные о найденных вхождениях и сверяя их на каждом новом шаге. По аналогии с поиском единственного вхождения, где мы сохраняем индекс и счётчик, увеличивая его или обнуляя в зависимости от текущего элемента первоначального массива, и возвращаем сохранённый индекс, когда счётчик достиг длины искомого подмассива.
Помогите, пожалуйста, развить сей алгоритм для нахождения всех вхождений заданного подмассива, а не только первого, так как мне в голову лезут какие-то бредовые идеи
UPD: Пример входных/выходных данных
- Массив: [1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3]
- Подмассив: [1, 2, 3]
- Выходные данные: [0, 6, 9]