Изменения

Перейти к: навигация, поиск

Наивный алгоритм поиска подстроки в строке

2 байта добавлено, 14:15, 6 мая 2014
Постановка задачи
==Постановка задачи==
Дан текст <tex>t[1 .. n]</tex> и паттерн <tex>p[1 .. m]</tex> такие, что <tex>n \geqslant m</tex> и элементы этих строк {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Говорят, что строка паттерн <tex>p</tex> встречается в строке тексте <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s + 1 .. s + m] = p[1..m].</tex> Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. Требуется проверить, входит ли паттерн <tex>p</tex> в текст <tex>t</tex>.
==Алгоритм==
668
правок

Навигация