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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
  |-
 
  |-
 
  |2
 
  |2
−
  |i
+
  |ippi
−
  |11
+
  |8
 
  |-
 
  |-
 
  |3
 
  |3
−
  |i
+
  |issippi
−
  |11
+
  |5
 
  |-
 
  |-
 
  |4
 
  |4
−
  |i
+
  |ississippi
−
  |11
+
  |2
 
  |-
 
  |-
 
  |5
 
  |5
−
  |i
+
  |mississippi
−
  |11
+
  |1
 
  |-
 
  |-
 
  |6
 
  |6
−
  |i
+
  |pi
−
  |11
+
  |10
 
  |-
 
  |-
 
  |7
 
  |7
−
  |i
+
  |ppi
−
  |11
+
  |9
 
  |-
 
  |-
 
  |8
 
  |8
−
  |i
+
  |sippi
−
  |11
+
  |7
 
  |-
 
  |-
 
  |9
 
  |9
−
  |i
+
  |sissippi
−
  |11
+
  |4
 
  |-
 
  |-
 
  |10
 
  |10
−
  |i
+
  |ssippi
−
  |11
+
  |6
 
  |-
 
  |-
 
  |11
 
  |11
−
  |i
+
  |ssissippi
−
  |11
+
  |3
 
  |-
 
  |-
 
  |}
 
  |}

Версия 01:20, 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].
Вот суффиксный массив для данной строки:

# суффикс номер суффикса
1 i 11
2 ippi 8
3 issippi 5
4 ississippi 2
5 mississippi 1
6 pi 10
7 ppi 9
8 sippi 7
9 sissippi 4
10 ssippi 6
11 ssissippi 3
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_поиска_подстроки_в_строке_с_помощью_суффиксного_массива&oldid=8459»