Алгоритм для линейного сопоставления с образцом?

У меня есть линейный список нулей и единиц, и мне нужно сопоставить несколько простых шаблонов и найти первое вхождение. Например, мне может понадобиться найти,000110110101010100100, ИЛИ ЖЕ10100100010 в списке длиной 8 миллионов. Мне нужно только найти первое вхождение любого из них, а затем вернуть индекс, по которому оно происходит. Тем не менее, выполнение циклов и доступ к большому списку может быть дорогим, и яЯ бы не хотел делать это слишком много раз.

Есть ли более быстрый метод, чем делать

foreach (patterns) {
    for (i=0; i < listLength; i++)
        for(t=0; t < patternlength; t++)
            if( list[i+t] != pattern[t] ) {
                 break;
            }
            if( t == patternlength - 1 ) {
                 return i;  // pattern found!
            }
        }
    }
}

Редактировать: Кстати, я реализовал эту программу в соответствии с приведенным выше псевдокодом, и производительность в порядке, но ничего впечатляющего. Я'Я предполагаю, что я обрабатываю около 6 миллионов бит в секунду на одном ядре моего процессора. Я'Я использую это для обработки изображений, и этоНам придется пройти через несколько тысяч 8-мегапиксельных изображений, так что каждый кусочек помогает.

Редактировать: Если оно'не ясно, яя работаю с битовым массивом, так чтоЕсть только две возможности: один и ноль. И это'в C ++.

Редактировать: Спасибо за указатели на алгоритмы BM и KMP. Я отметил, что на странице Википедии для BM это говорит

Алгоритм предварительно обрабатывает искомую целевую строку (ключ), но не искомую строку (в отличие от некоторых алгоритмов, которые предварительно обрабатывают искомую строку и могут затем амортизировать затраты на предварительную обработку путем повторного поиска).

Это выглядит интересно, но это не такПриведите примеры таких алгоритмов. Может ли что-то подобное помочь?

Ответы на вопрос(5)

Ваш ответ на вопрос