Цена излишних усилий: строковый поиск

Это перевод The cost of trying too hard: String searching. Автор: Реймонд Чен.

Есть много алгоритмов быстрого поиска строк, но работа строкового поиска, по сути, O(n), где n - это длина строки, в которой ищут: если m - длина образца (который я называю "целевой строкой"), то любой алгоритм, который проверяет менее n/m элементов, оставляет "дырку" в m непроверенных элементов, что является достаточным местом, чтобы спрятать там строку.

Более продвинутые алгоритмы поиска строк могут воспользоваться некоторыми характеристиками целевой строки, но в общем случае, когда целевая строка имеет средний размер и не патологична, все эти модные алгоритмы поиска дадут ваш выигрыш над наивным алгоритмом поиска в виде небольшого множителя (константы).

В подавляющем большинстве случаев наивный алгоритм поиска является адекватным. Пока вы ищете нормальные строки из практики, а не краевые случаи вроде "Найди aaaaaaaaaaaaaaab в строке aaaaaaaaaaaaaabaaaaaaaaaaaaaaab". Если ваша целевая строка само-подобна, то наивный алгоритм поиска строки даст вам O(mn), где m - длина целевой строки. И эффект от продвинутого алгоритма поиска заключается в нейтрализации множителя m, но за это вам придётся заплатить предварительным анализом целевой строки. Если вы ищете "относительно короткие" "нормальные" строки, то выгода от применения сложного алгоритма поиска может не перевесить затраты на первоначальный анализ.

Вот почему почти все библиотеки функций, которым нужно выполнять строковый поиск, используют наивный алгоритм поиска. Потому что он является подходящим решением более чем в 99% случаев.