Алгоритм пошуку рядка

${\displaystyle \;\Sigma ^{*}}$ — множина всіх рядків скінченної довжини, утворенних за допомогою символів алфавіту ${\displaystyle \;\Sigma }$. Порожній рядок ${\displaystyle \;\varepsilon }$ також належить ${\displaystyle \;\Sigma ^{*}}$.

Довжина рядка ${\displaystyle \;x}$ позначається як ${\displaystyle |x|\;}$. Конкатенація (об'єднання) двох рядків ${\displaystyle \;x}$ і ${\displaystyle \;y}$ записується як ${\displaystyle \;xy}$, її довжина відповідно дорівнює ${\displaystyle \;|x|+|y|}$. Конкатенація складається з символів рядка ${\displaystyle \;x}$ після яких записані символи рядка ${\displaystyle \;y}$.

Приклад:

${\displaystyle \;x=\{abc\}}$

${\displaystyle \;y=\{def\}}$

${\displaystyle \;xy=\{abcdef\}}$

Рядок ${\displaystyle \;\omega }$ називається префіксом рядка ${\displaystyle \;x}$ (позначається ${\displaystyle \omega \sqsubset x}$), якщо ${\displaystyle \exists y\in \Sigma ^{*},x=\omega y}$. Якщо ${\displaystyle \omega \sqsubset x}$, то ${\displaystyle |\omega |\leq |x|}$.

Аналогічно, рядок ${\displaystyle \;\omega }$ називається суфіксом рядка ${\displaystyle \;x}$ (позначається ${\displaystyle \omega \sqsupset x}$), якщо ${\displaystyle \exists y\in \Sigma ^{*},x=y\omega }$.

Пустий рядок є одночастно префіксом і суфіксом будь-якого рядка.

Відношення ${\displaystyle \sqsubset }$ і ${\displaystyle \sqsupset }$ є транзитивними.

Припустимо, що ${\displaystyle \;x}$, ${\displaystyle \;y}$ і ${\displaystyle \;z}$ — рядки, для яких виконується співвідношення ${\displaystyle x\sqsubset z}$ і ${\displaystyle y\sqsubset z}$. Тоді, якщо ${\displaystyle |x|\leq |y|}$, то ${\displaystyle x\sqsubset y}$; якщо ${\displaystyle |x|\geq |y|}$, то ${\displaystyle y\sqsubset x}$. Якщо ${\displaystyle \;|x|=|y|}$, то ${\displaystyle \;x=y}$.

Доведення: Всі три випадки розібрані на малюнку:

Позначимо k-символьний префікс ${\displaystyle \;P[1..k]}$ зразка ${\displaystyle \;P[1..m]}$ через ${\displaystyle \;P_{k}}$. Таким чином, ${\displaystyle \;P_{0}=\varepsilon }$ і ${\displaystyle \;P_{m}=P=P[1..m]}$. Аналогічно через ${\displaystyle \;T_{k}}$ позначимо k-символьний префікс тексту ${\displaystyle \;T}$.

За допомогою цих позначень, задачу пошуку рядка можна сформулювати, як задачу виявлення всіх зсувів ${\displaystyle 0\leq s\leq n-m}$, таких що, ${\displaystyle P\sqsupset T_{s+m}}$.

• Алгоритм Ахо — Корасік
• Алгоритм Коменц-Вальтер
• Алгоритм Рабіна-Карпа

Для пошуку зразків, що утворюють нескінченну (або дуже велику) множину, користуються формальними граматиками і регулярними виразами.

Швидкі алгоритми пошуку використовують передобробку тексту. Входження зразка може бути швидко знайдене, якщо для тексту побудувати індекс підрядків (наприклад, суфіксне дерево чи суфіксний масив). Так, суфіксне дерево можна побудувати за час Θ(n), а всі z входжень зразка можна знайти за час O(n + z) (якщо вважати, що розмір алфавіту — константа).

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