130
правок
Изменения
Псевдокод
'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.
По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>\lvert |s\rvert| =n</tex>) содержатся все строки <tex>s[1..\mathinner{\ldotp\ldotp} n], ...\dotsc, s[n..\mathinner{\ldotp\ldotp} n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i..\mathinner{\ldotp\ldotp} n]</tex>, то все ее её префиксы <tex>s[i..\mathinner{\ldotp\ldotp} j]</tex> (<tex>i \le leqslant j \le leqslant n</tex>) уже содержатся в боре.
==Применение==
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
== Реализация ==
'''struct Trie'''
'''Addstruct Node'''(i, j) current <tex>\leftarrow</tex> 0 '''formap<char, Node>''' (char c <tex>\in</tex> s[i..j]) if (!trie[current].containsKey(c)) trie[current].add(c, number) number++; current <tex>\leftarrow</tex> trie[current][c]children
'''Buildfun'''add(String s: '''string''') '''Node''' current = root '''for'''c '''in''' s '''if''' current.children[c] == <tex>\varnothing</tex> current.children[c] = '''new Node''' current = current.children[c] '''fun''' build(s: '''string''') root = '''new Node''' '''int ''' n = s.size '''for''' i = 0, i < 1 '''to''' n, i++) Addadd(s[i, ..n])
==Оценки использования памяти==
