В соответствии с запись в википедии по алгоритму соответствия строк Rabin-Karp, его можно использовать для поиска нескольких разных шаблонов в строке на одновременно сохраняя линейную сложность. Понятно, что это легко сделать, когда все шаблоны имеют одинаковую длину, но я до сих пор не понимаю, как мы можем сохранить сложность O (n) при одновременном поиске шаблонов с различной длиной. Может кто-то пролить свет на это?
Изменить (декабрь 2011):
С тех пор статья wikipedia была обновлена и больше не претендует на соответствие нескольким шаблонам различной длины в O (n).