Подстрока

Подстрока — непустая связная часть строки: если $L=c_{0}\dots c_{n-1}$ — строка длины $n$, то любая строка $S=c_{i}\dots c_{j}$, где $0\leqslant i\leqslant j\leqslant n-1$, является подстрокой $L$ длины $j-i+1$. Если $i=0$, то $S$ называется префиксом $L$ длины $j+1$, если $j=n-1$, то $S$ — суффикс $L$ длины $j-i+1$.

Например, строки «кипед», «Вики», «дия» являются подстроками строки «Википедия»; при этом «Вики» — префиксом, а «дия» — суффиксом:

Википедия
|||||||||
||кипед||
||||  |||
Вики  |||
      дия

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

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.