Какой самый быстрый алгоритм поиска подстроки?

Итак, я не похож на идиота, я собираюсь изложить проблему / требования более четко:

• Игла (образец) и стог сена (текст для поиска) - строки с нулевым окончанием в стиле C. Информация о длине не предоставляется; если необходимо, оно должно быть вычислено.
• Функция должна вернуть указатель на первое совпадение или, NULLесли совпадение не найдено.
• Случаи отказа не допускаются. Это означает, что любой алгоритм с непостоянными (или большими постоянными) требованиями к хранилищу должен иметь запасной вариант для сбоя выделения (и, следовательно, производительность в резервном режиме повышает производительность в худшем случае).
• Реализация должна быть на C, хотя хорошее описание алгоритма (или ссылка на него) без кода тоже подойдет.

... а также то, что я имею в виду под "самым быстрым":

• Детерминированный O(n)где n= длина стога сена. (Но может быть возможно использовать идеи из алгоритмов, которые обычно O(nm)(например, скользящий хэш), если они объединены с более надежным алгоритмом для получения детерминированных O(n)результатов).
• Никогда не работает (измеримо; пара часов if (!needle[1])и т. Д. В порядке) хуже, чем алгоритм наивной грубой силы, особенно на очень коротких иглах, которые, вероятно, являются наиболее распространенным случаем. (Безусловные тяжелые накладные расходы на предварительную обработку плохие, так как пытаются улучшить линейный коэффициент для патологических игл за счет вероятных игл.)
• Учитывая произвольную иголку и стог сена, сопоставимая или лучшая производительность (не хуже, чем на 50% больше времени поиска) по сравнению с любым другим широко реализованным алгоритмом.
• Помимо этих условий, я оставляю определение «самый быстрый» открытый. Хороший ответ должен объяснить, почему вы считаете подход, который вы предлагаете, «самым быстрым».

Моя текущая реализация работает примерно на 10% медленнее и в 8 раз быстрее (в зависимости от ввода), чем реализация glibc Two-Way.

Обновление: мой текущий оптимальный алгоритм выглядит следующим образом:

• Для игл длиной 1 используйте strchr.
• Для игл длиной 2-4 используйте машинные слова, чтобы сравнить 2-4 байта одновременно следующим образом: предварительно загрузить иглу в 16- или 32-битное целое число со смещениями и циклически выводить старые байты / новые байты из стога сена на каждой итерации , Каждый байт стога сена читается ровно один раз и выполняет проверку на 0 (конец строки) и одно 16- или 32-битное сравнение.
• Для игл длиной> 4 используйте двусторонний алгоритм с плохой таблицей сдвига (например, Бойера-Мура), который применяется только к последнему байту окна. Чтобы избежать затрат на инициализацию таблицы размером 1 Кб, что может привести к чистым потерям для многих игл средней длины, я сохраняю битовый массив (32 байта), отмечающий, какие записи в таблице сдвига инициализированы. Биты, которые не установлены, соответствуют значениям байтов, которые никогда не появляются в игле, для которых возможен полный сдвиг длины иглы.

Большие вопросы, которые остались в моей голове:

• Есть ли способ лучше использовать таблицу плохих смен? Бойер-Мур лучше всего использует его, сканируя в обратном направлении (справа налево), но для двухстороннего сканирования требуется сканирование слева направо.
• Единственные два жизнеспособные алгоритмы кандидатов , которые я нашел в общем случае (не из- за нехватками памяти или квадратичных условий исполнения) являются двухсторонние и Струнный Matching на упорядоченных алфавитах . Но есть ли легко обнаруживаемые случаи, когда разные алгоритмы были бы оптимальными? Конечно, многие из O(m)(где mдлина иглы) в космических алгоритмах могут быть использованы для m<100или около того. Также было бы возможно использовать алгоритмы, являющиеся квадратичными в худшем случае, если бы существовал простой тест для игл, который доказуемо требует только линейного времени.

Бонусные баллы за:

• Можете ли вы улучшить производительность, если предположить, что игла и стог сена хорошо сформированы UTF-8? (С символами различной длины байтов правильная форма накладывает некоторые требования к выравниванию строк между иглой и стогом сена и позволяет автоматически сдвигать 2-4 байта, когда встречается несоответствующий главный байт. Но действительно ли эти ограничения дают вам многое / что-либо помимо того, что вычисления максимального суффикса, хорошие сдвиги суффиксов и т. д. уже дают вам различные алгоритмы?)

Примечание: я хорошо знаю большинство алгоритмов, но не знаю, насколько хорошо они работают на практике. Вот хороший справочник, чтобы люди не давали мне ссылки на алгоритмы в виде комментариев / ответов: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

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

Бойер-Мур использует плохую таблицу символов с хорошей таблицей суффиксов.

Бойер-Мур-Хорспул использует таблицу плохих персонажей.

Кнут-Моррис-Пратт использует таблицу частичных совпадений.

Рабин-Карп использует бегущие хеши.

Все они тратят накладные расходы на уменьшение сравнения в разной степени, поэтому реальная производительность будет зависеть от средней длины иглы и стога сена. Чем больше начальных затрат, тем лучше при более длинных входах. С очень короткими иглами, грубая сила может победить.

Редактировать:

Другой алгоритм может быть лучше для поиска пар оснований, английских фраз или отдельных слов. Если бы был один лучший алгоритм для всех входных данных, он был бы опубликован.

Подумайте о следующем столике. Каждый знак вопроса может иметь свой лучший алгоритм поиска.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

Это действительно должен быть график с диапазоном от коротких до длинных входов по каждой оси. Если бы вы построили каждый алгоритм на таком графике, у каждого была бы своя сигнатура. Некоторые алгоритмы страдают от большого количества повторений в шаблоне, что может повлиять на использование, такое как поиск генов. Некоторые другие факторы, влияющие на общую производительность, - это поиск одного и того же шаблона более одного раза и одновременный поиск различных шаблонов.

Если бы мне понадобился набор образцов, я думаю, что я бы очистил сайт, такой как Google или Википедия, а затем убрал бы html со всех страниц результатов. Для поиска сайта введите слово, а затем используйте одну из предложенных поисковых фраз. Выберите несколько разных языков, если это применимо. Используя веб-страницы, все тексты будут короткими и средними, поэтому объедините достаточно страниц, чтобы получить более длинные тексты. Вы также можете найти общедоступные книги, юридические записи и другие крупные текстовые материалы. Или просто генерировать случайный контент, выбирая слова из словаря. Но цель профилирования - проверить тип контента, который вы будете искать, поэтому по возможности используйте примеры из реального мира.

Я оставил короткий и длинный расплывчатый. Что касается иглы, я думаю о коротких менее 8 символов, средних до 64 символов и длиной до 1 КБ. Для стога сена, я думаю, короткий как 2 ^ 10, средний как под 2 ^ 20, и длиной до 2 ^ 30 символов.

Опубликованный в 2011 году, я считаю, что он вполне может быть алгоритмом «Простое сопоставление строк в постоянном пространстве в реальном времени» Дэни Бреслауэра, Роберто Гросси и Филиппо Миньоси.

Обновить:

В 2014 году авторы опубликовали это улучшение: на пути к оптимальному сопоставлению упакованных строк .

Http://www-igm.univ-mlv.fr/~lecroq/string/index.html ссылки вы указываете является отличным источником и резюме некоторых из наиболее известных и изученных алгоритмов сопоставления строк.

Решения большинства проблем поиска включают компромиссы в отношении затрат на предварительную обработку, времени и пространства. Ни один алгоритм не будет оптимальным или практичным во всех случаях.

Если ваша цель состоит в том, чтобы разработать конкретный алгоритм поиска строк, тогда не обращайте внимания на то, что я должен сказать: если вы хотите разработать обобщенную подпрограмму службы поиска строк, попробуйте следующее:

Потратьте некоторое время на изучение конкретных сильных и слабых сторон алгоритмов, на которые вы уже ссылались. Проведите обзор, чтобы найти набор алгоритмов, которые охватывают диапазон и область поиска строк, которые вас интересуют. Затем создайте селектор внешнего поиска на основе функции классификатора, чтобы выбрать лучший алгоритм для заданных входных данных. Таким образом, вы можете использовать наиболее эффективный алгоритм для выполнения работы. Это особенно эффективно, когда алгоритм очень хорош для определенных поисков, но плохо ухудшается. Например, грубая сила, вероятно, является наилучшей для игл длиной 1, но быстро ухудшается с увеличением длины иглы, после чего sustik-moore algoritimможет стать более эффективным (для маленьких алфавитов), тогда для более длинных игл и больших алфавитов алгоритмы KMP или Бойера-Мура могут быть лучше. Это всего лишь примеры, иллюстрирующие возможную стратегию.

Многофункциональный подход не новая идея. Я полагаю, что он использовался несколькими коммерческими пакетами сортировки / поиска (например, SYNCSORT, обычно используемый на мэйнфреймах, реализует несколько алгоритмов сортировки и использует эвристику для выбора «лучшего» для заданных входов)

Каждый алгоритм поиска имеет несколько вариантов, которые могут существенно повлиять на его производительность, как, например, показано в этой статье .

Оцените свой сервис, чтобы классифицировать области, где требуются дополнительные стратегии поиска, или для более эффективной настройки функции выбора. Этот подход не является быстрым или легким, но, если все сделано правильно, может дать очень хорошие результаты.

Я был удивлен, увидев наш технический отчет, цитируемый в этой дискуссии; Я являюсь одним из авторов алгоритма, который был назван Сустик-Мур выше. (Мы не использовали этот термин в нашей статье.)

Я хотел здесь подчеркнуть, что для меня наиболее интересной особенностью алгоритма является то, что довольно просто доказать, что каждая буква проверяется не более одного раза. Для более ранних версий Бойера-Мура они доказали, что каждая буква проверяется не более 3, а затем не более 2 раз, и эти доказательства были более сложными (см. Ссылки в статье). Поэтому я также вижу дидактическую ценность в представлении / изучении этого варианта.

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

Нашей главной целью было довести эту версию до сведения тех, кто может улучшить ее. Поиск строк имеет так много вариаций, и мы сами не можем придумать, где эта идея может принести пользу. (Фиксированный текст и изменение шаблона, фиксированный шаблон другого текста, предварительная обработка возможна / невозможна, параллельное выполнение, поиск подходящих подмножеств в больших текстах, допустимые ошибки, близкие совпадения и т. Д. И т. Д.)

Самый быстрый алгоритм поиска подстроки будет зависеть от контекста:

1. размер алфавита (например, ДНК против английского)
2. длина иглы

Документ 2010 года «Проблема точного сопоставления строк: комплексная экспериментальная оценка» приводятся таблицы со временем выполнения для 51 алгоритма (с различными размерами алфавита и длиной иглы), поэтому вы можете выбрать лучший алгоритм для вашего контекста.

Все эти алгоритмы имеют реализации C, а также набор тестов, здесь:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Действительно хороший вопрос. Просто добавьте крошечные кусочки ...

1. Кто-то говорил о совпадении последовательностей ДНК. Но для последовательности ДНК мы обычно строим структуру данных (например, массив суффиксов, дерево суффиксов или индекс FM) для стога сена и сопоставляем множество игл с ним. Это другой вопрос.

2. Было бы здорово, если бы кто-то хотел сравнить различные алгоритмы. Существуют очень хорошие тесты для сжатия и построения массивов суффиксов, но я не видел тестов для сравнения строк. Потенциальные кандидаты в стог сена могут быть из эталона SACA .

3. Несколько дней назад я тестировал реализацию Бойера-Мура со страницы, которую вы рекомендовали (РЕДАКТИРОВАТЬ: мне нужен вызов функции, такой как memmem (), но это не стандартная функция, поэтому я решил ее реализовать). Моя программа бенчмаркинга использует случайный стог сена. Кажется, что реализация Boyer-Moore на этой странице в разы быстрее, чем у glibc memmem () и Mac strnstr (). В случае, если вам интересно, реализация здесь, а код для тестирования здесь . Это определенно не реалистичный ориентир, но это начало.

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

Используйте stdlib strstr:

char *foundit = strstr(haystack, needle);

Это было очень быстро, мне потребовалось около 5 секунд, чтобы напечатать.

Вот поисковая реализация Python , используемая во всем ядре. Комментарии указывают, что он использует сжатую таблицу дельты Бойера-Мура .

Я провел довольно обширный эксперимент с поиском строк, но это было для нескольких строк поиска. Реализации Монтажные Horspool и Bitap часто могут проводить свои собственные против алгоритмов как Ахо-Corasick для низкого количества шаблонов.

Более быстрый strchrалгоритм «Поиск одного подходящего символа» (ala ).

Важные заметки:

• Эти функции используют «число / количество (ведущих | конечных) нулей» gcc встроенный компилятор__builtin_ctz . Эти функции могут быть быстрыми только на машинах, на которых есть инструкция (ы), выполняющая эту операцию (например, x86, ppc, arm).

• Эти функции предполагают, что целевая архитектура может выполнять 32- и 64-битные невыровненные нагрузки. Если ваша целевая архитектура не поддерживает это, вам нужно будет добавить некоторую логику запуска, чтобы правильно выровнять показания.

• Эти функции нейтральны по отношению к процессору. Если у целевого ЦП есть векторные инструкции, вы могли бы сделать (намного) лучше. Например, strlenприведенная ниже функция использует SSE3 и может быть тривиально изменена на XOR отсканированных байтов для поиска байта, отличного от0 . Тесты производительности на ноутбуке Core 2 с частотой 2,66 ГГц и Mac OS X 10.6 (x86_64):

  • 843,433 МБ / с для strchr
  • 2656,742 МБ / с для findFirstByte64
  • 13094,479 МБ / с для strlen

... 32-битная версия:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... и 64-битная версия:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Изменить 2011/06/04 ОП отмечает в комментариях, что это решение имеет «непреодолимую ошибку»:

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

Технически это верно, но применимо практически к любому алгоритму, который работает с блоками, размер которых превышает один байт, включая метод, предложенный ФП в комментариях:

Типичная strchrреализация не наивна, но немного более эффективна, чем вы дали. Смотрите конец этого для наиболее широко используемого алгоритма: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

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

Но это не «ошибка» в алгоритме, приведенном в ответе, - такое поведение вызвано тем, что функции любят strchrи strlenне принимают lengthаргумент для ограничения размера поиска. Поиск char bytes[1] = {0x55};, который для целей нашего обсуждения именно так и происходит, размещается в самом конце границы страницы 4K VM, а следующая страница не отображается, с strchr(bytes, 0xAA)(где реализация strchrвыполняется по байтам за раз), что приведет к сбою точно так же. То же самое для strchrродственникаstrlen .

Без lengthаргумента невозможно определить, когда следует переключиться с высокоскоростного алгоритма и вернуться к побайтовому алгоритму. Гораздо более вероятной «ошибкой» будет чтение «за пределами размера выделения», что технически приводит undefined behaviorк различным стандартам языка C и будет помечено как ошибка чем-то вроде valgrind.

Таким образом, все, что работает с блоками больше, чем байты, работает быстрее, как это делает код ответа и код, указанный OP, но должно иметь семантику считывания с точностью до байта, вероятно, будет "глючным", если нет lengthаргумента для контролировать угловой случай (ы) «последнего чтения».

Код в этом ответе - это ядро, позволяющее быстро найти первый байт в блоке естественного размера слова ЦП, если у целевого ЦП есть ctzинструкция быстрого типа. Тривиально добавить такие вещи, как проверка того, что он работает только на правильно выровненных естественных границах, или некоторая формаlength границ, которые позволят вам переключиться из высокоскоростного ядра и в более медленную побайтовую проверку.

ФП также заявляет в комментариях:

Что касается вашей оптимизации ctz, она имеет значение только для хвостовой операции O (1). Это может улучшить производительность с крошечными строками (например, strchr("abc", 'a');но никак не со строками любого большого размера).

Верно ли это утверждение, во многом зависит от микроархитектуры. Используя каноническую четырехступенчатую модель RISC-конвейера, это почти наверняка верно. Но очень трудно сказать, верно ли это для современного суперскалярного процессора высшего порядка, где скорость ядра может значительно снизить скорость потоковой памяти. В этом случае это не только правдоподобно, но и довольно часто, поскольку существует большой разрыв в «количестве инструкций, которые могут быть удалены» относительно «количества байтов, которые могут быть переданы« так, чтобы вы имели » количество команд, которые могут быть удалены для каждого байта, который может быть передан ". Если он достаточно велик, ctzинструкцию + shift можно выполнить «бесплатно».

Просто найдите «самый быстрый strstr», и если вы видите что-то интересное, просто спросите меня.

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

Просто быстрый пример:

Ведение поиска шаблона (32 байт) в строке (206908949bytes) как-однострочный ... Skip-Performance (больше-The-лучше): 3041%, 6801754 скачет / итерация Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade производительность: 3483KB / Часы

Выполнение поиска по шаблону (32 байта) в строку (206908949 байтов) в виде одной строки ... Пропускная способность (чем больше, тем лучше): 1554%, 13307181 пропусков / итераций Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Производительность Boyer_Moore_Flensburg : 24 / 83KK : Часы

Выполнение поиска шаблона (32 байта) в строку (206908949 байтов) в одну строку ... Пропускная способность (чем больше, тем лучше): 129%, 160239051 пропусков / итераций Two-Way_hits / Two-Way_clocks: 0/816 Two -Производительность : 247 КБ / час

Санмайс,
С уважением

Двусторонний алгоритм, который вы упоминаете в своем вопросе (который, кстати, невероятен!), Недавно был улучшен для эффективной работы с многобайтовыми словами за раз: оптимальное сопоставление упакованных строк .

Я не читал всю статью, но кажется, что они полагаются на пару новых специальных инструкций ЦП (включенных, например, в SSE 4.2), обозначающих O (1), для их требования по сложности времени, хотя, если они недоступны, они могут смоделируйте их за O (log log w) для w-битных слов, что звучит не так уж плохо.

Вы могли бы реализовать, скажем, 4 разных алгоритма. Каждые М минут (которые будут определены опытным путем) запускают все 4 на текущих реальных данных. Накопить статистику по N прогонов (также TBD). Затем используйте только победителя в течение следующих M минут.

Регистрируйте статистику побед, чтобы вы могли заменить алгоритмы, которые никогда не побеждают, новыми. Сконцентрируйте усилия по оптимизации на самой выигрышной рутине. Обратите особое внимание на статистику после любых изменений в оборудовании, базе данных или источнике данных. Включите эту информацию в журнал статистики, если это возможно, так что вам не придется вычислять ее по дате / времени.

Недавно я обнаружил хороший инструмент для измерения производительности различных доступных алгоритмов: http://www.dmi.unict.it/~faro/smart/index.php

Вы можете найти это полезным. Кроме того, если мне нужно быстро вызвать алгоритм поиска подстроки, я бы выбрал Кнут-Моррис-Пратт.

Возможно, вы также захотите иметь различные тесты с несколькими типами строк, так как это может сильно повлиять на производительность. Алгоритмы будут выполнять различие, основанное на поиске естественного языка (и даже здесь все еще могут быть мелкозернистые различия из-за различных морфологий), строк ДНК или случайных строк и т. Д.

Размер алфавита будет играть роль во многих алгоритмах, как и размер иглы. Например, Хорспул хорошо работает с английским текстом, но плохо с ДНК из-за разного размера алфавита, что усложняет жизнь правилу плохих персонажей. Введение хорошего суффикса значительно облегчает это.

Я не знаю, является ли это абсолютным лучшим, но у меня был хороший опыт с Бойер-Муром .

Это не дает прямого ответа на вопрос, но если текст очень большой, как насчет разделения его на перекрывающиеся разделы (перекрывающиеся по длине шаблона), а затем одновременно ищите разделы, используя потоки. Что касается самого быстрого алгоритма, Бойер-Мур-Хорспул, я думаю, является одним из самых быстрых, если не самый быстрый среди вариантов Бойер-Мур. Я опубликовал пару вариантов Бойера-Мура (я не знаю их названия) в этой теме Алгоритм быстрее, чем поиск BMH (Бойера-Мура-Хорспула) .

Самым быстрым в настоящее время является EPSM С. Фаро и О. М. Кулекчи. Видеть Http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm.

«Точное совпадение упакованных строк» ​​оптимизировано для SIMD SSE4.2 (x86_64 и aarch64). Он работает стабильно и лучше всех размеров.

Сайт, на который я ссылался, сравнивает 199 быстрых алгоритмов поиска строк, с обычными (BM, KMP, BMH) довольно медленными. EPSM превосходит все остальные, упомянутые здесь на этих платформах. Это также последний.