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

У меня есть линейный список нулей и единиц, и мне нужно сопоставить несколько простых шаблонов и найти первое вхождение. Например, мне может понадобиться найти0001101101, 01010100100, ИЛИ ЖЕ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!
            }
        }
    }
}

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

Edit: Если неясно, я работаю с битовым массивом, так что есть только две возможности: ОДИН и НУЛЕВЫЙ. И это в C ++.

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

The algorithm preprocesses the target string (key) that is being searched for, but not the string being searched in (unlike some algorithms that preprocess the string to be searched and can then amortize the expense of the preprocessing by searching repeatedly).

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

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

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