Наивный алгоритм поиска подстроки в строке — различия между версиями
Sergej (обсуждение | вклад) (→Преимущества) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 23 промежуточные версии 5 участников) | |||
Строка 1: | Строка 1: | ||
− | = | + | {{Задача |
− | + | |definition = Дан текст <tex>t[0 \,\mathinner{\ldotp\ldotp}\, n-1]</tex> и паттерн <tex>p[0 \,\mathinner{\ldotp\ldotp}\, m-1]</tex> такие, что <tex>n \geqslant m</tex> и элементы этих строк {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Требуется проверить, входит ли паттерн <tex>p</tex> в текст <tex>t</tex>. | |
+ | }} | ||
+ | {{Определение | ||
+ | |definition = Будем говорить, что паттерн <tex>p</tex> встречается в тексте <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex>. Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. | ||
+ | }} | ||
==Алгоритм== | ==Алгоритм== | ||
− | В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>t[s | + | В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие |
+ | <tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex> для каждого из <tex> n - m + 1 </tex> возможных значений <tex>s</tex>. | ||
− | ==Псевдокод== | + | ===Псевдокод=== |
Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения. | Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения. | ||
− | '''vector<int>''' naiveStringMatcher ('''string''' | + | '''vector<int>''' naiveStringMatcher(t : '''string''', p : '''string'''): |
'''int''' n = t.length | '''int''' n = t.length | ||
'''int''' m = p.length | '''int''' m = p.length | ||
'''vector<int>''' ans | '''vector<int>''' ans | ||
− | '''for''' i = | + | '''for''' i = 0 '''to''' n - m |
− | '''if''' | + | '''if''' t[i .. i + m - 1] == p |
− | + | ans.push_back(i) | |
'''return''' ans | '''return''' ans | ||
− | ==Время работы== | + | ===Время работы=== |
− | Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex | + | Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex>\dfrac{n}{2}</tex>, что даёт <tex> O\left(\dfrac{n^2}{4}\right) = O\left(n^2\right) </tex>. |
+ | Однако если <tex>m</tex> достаточно мало по сравнению с <tex>n</tex>, то тогда асимптотика получается близкой к <tex>O(n)</tex>, поэтому этот алгоритм достаточно широко применяется на практике. | ||
− | ==Преимущества== | + | == Сравнение с другими алгоритмами == |
+ | === Преимущества === | ||
+ | * Требует <tex>O(1)</tex> памяти. | ||
+ | * Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти. | ||
+ | * Простая и понятная реализация. | ||
+ | === Недостатки === | ||
+ | * Требует <tex>O(m \cdot (n-m))</tex> операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше). | ||
− | + | == Источники информации == | |
− | + | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034. | |
− | |||
− | |||
− | == | ||
− | * ''Кормен | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Поиск подстроки в строке]] | [[Категория:Поиск подстроки в строке]] | ||
+ | [[Категория:Точный поиск]] |
Текущая версия на 19:07, 4 сентября 2022
Задача: |
Дан текст | и паттерн такие, что и элементы этих строк — символы из конечного алфавита . Требуется проверить, входит ли паттерн в текст .
Определение: |
Будем говорить, что паттерн | встречается в тексте со сдвигом , если и . Если строка встречается в строке , то является подстрокой .
Алгоритм
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие
для каждого из возможных значений .Псевдокод
Приведем пример псевдокода, который находит все вхождения строки
в и возвращает массив позиций, откуда начинаются вхождения.vector<int> naiveStringMatcher(t : string, p : string): int n = t.length int m = p.length vector<int> ans for i = 0 to n - m if t[i .. i + m - 1] == p ans.push_back(i) return ans
Время работы
Алгоритм работает за
. В худшем случае , что даёт . Однако если достаточно мало по сравнению с , то тогда асимптотика получается близкой к , поэтому этот алгоритм достаточно широко применяется на практике.Сравнение с другими алгоритмами
Преимущества
- Требует памяти.
- Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании Ctrl + F), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
- Простая и понятная реализация.
Недостатки
- Требует операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше).
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034.