Алгоритмы поиска строки
Для двух алгоритмов поиска строки: KMP и суффиксное дерево, которое предпочтено в который случаи? Дайте некоторые практические примеры.
1 ответ
Суффиксное дерево лучше, если вам придется отвечать на множество запросов типа "есть ли иголка в стоге сена?". KMP лучше, если вам нужно искать только одну строку в другой единственной строке, а не делать это много раз.
Суффиксное дерево - это гораздо более общая структура данных, поэтому с ним можно делать гораздо больше. Посмотрите, что можно сделать с ним здесь. KMP полезен для поиска того, является ли строка подстрокой в другой строке.
Возможно, вы также захотите проверить другие алгоритмы, такие как Boyer-Moore, Rabin-Karp и даже наивный алгоритм, поскольку есть ситуации (исходные данные), в которых один из них лучше других.
Итог таков:
- Если у вас много запросов, подобных тому, о котором я говорил выше, стоит построить суффиксное дерево и затем отвечать на каждый запрос быстрее.
- Если вам нужно выполнять не только эти типы запросов, суффиксное дерево также стоит построить.
- Если вам важно лишь изредка находить, является ли строка подстрокой другой строки, то используйте KMP.