Индекс подстрок

Индекс подстрок — это структура данных, позволяющая производить поиск подстроки в тексте или наборе текстов за сублинейное время. Это значит, что имея документ $\text{[math]}$ $\text{[math]}$ $S$ $S$ длины $\text{[math]}$ $\text{[math]}$ $n$ $n$ или набор документов $\text{[math]}$ $\text{[math]}$ $D=\{S^{1},S^{2},\dots ,S^{d}\}$ $D=\{S^{1},S^{2},\dots ,S^{d}\}$ общей длины $\text{[math]}$ $\text{[math]}$ $n$ $n$ , вы можете найти все вхождения образца $\text{[math]}$ $\text{[math]}$ $P$ $P$ за $\text{[math]}$ $\text{[math]}$ $o(n)$ $o(n)$ (См. O-нотация). Словосочетание полнотекстовый индекс также иногда используется для обозначения индекса всех подстрок текста, но является неоднозначным, так как также используется для обозначения обычных индексов слов, например, инвертированного индекса.

Некоторые индексы подстрок: