Подстрока==Постановка задачи==Имеются строки <tex>T[1 .. n]</tex> и <tex>P[1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>m</tex> и элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>P</tex> встречается в строке <tex>T</tex> со сдвигом <tex>s</tex>, если <tex> 0 \le s \le n-m</tex> и <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex>. Если строка <tex>P</tex> встречается в строке <tex>T</tex>, то <tex>P</tex> является подстрокой <tex>T</tex>. Требуется проверить, является ли строка <tex>P</tex> подстрокой <tex>T</tex>. ==Алгоритм==В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex> для каждого из <tex> n-m+1</tex> возможных значений <tex>s</tex>. ==Псевдокод== '''Naive_String_Matcher''' (<tex>T,P</tex>) <tex>n \leftarrow length[T]</tex> <tex>m \leftarrow length[P]</tex> '''for''' <tex>s \leftarrow 0</tex> to <tex>n - m</tex> '''do if''' <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex> '''then''' print() == Литература ==* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
