Алгоритм поиска подстроки в строке с помощью суффиксного массива — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
Строка 1: Строка 1:
 +
Рассмотрим такую задачу: у нас есть образец <tex> p </tex>, строка <tex> s </tex>, [[суффиксный массив|суффиксный массив]] <tex> array </tex>, построенный для строки <tex> s </tex>. Необходимо найти все вхождения образца <tex> p </tex> в строку <tex> s </tex>.
  
 +
Для наглядности рассмотрим образец <tex> iss </tex> и строку <tex> mississippi </tex>. Вот суффиксный массив для данной строки:

Версия 01:07, 8 мая 2011

Рассмотрим такую задачу: у нас есть образец [math] p [/math], строка [math] s [/math], суффиксный массив [math] array [/math], построенный для строки [math] s [/math]. Необходимо найти все вхождения образца [math] p [/math] в строку [math] s [/math].

Для наглядности рассмотрим образец [math] iss [/math] и строку [math] mississippi [/math]. Вот суффиксный массив для данной строки:

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_поиска_подстроки_в_строке_с_помощью_суффиксного_массива&oldid=8457»