Подстрока — непустая связная часть строки: если — строка длины , то любая строка , где , является подстрокой длины . Если , то называется префиксом длины , если , то — суффикс длины .
Например, строки «кипед», «Вики», «дия» являются подстроками строки «Википедия»; при этом «Вики» — префиксом, а «дия» — суффиксом:
Википедия
||кипед||
Вики ||| дия
Поиск подстроки — одна из основополагающих алгоритмических задач информационного поиска, заключающаяся в нахождении позиции (индекса) первого вхождения образца. Существует обширный класс алгоритмов, реализующих поиск подстроки с различной эффективностью по времени и по памяти, среди них — алгоритмы Кнута — Морриса — Пратта, Бойера — Мура, Рабина — Карпа, Ахо — Корасик.
Литература
Категория:Строковые алгоритмы