Suffix array, LCP, suffix tree ve FM-index

Suffix array bir metnin bütün suffix başlangıç indekslerini lexicographic sırada tutar. Suffix'leri tam string kopyasıyla üretmek quadratic bellek doğurabilir; indeks tabanlı construction gerekir. Doubling yaklaşımı 1,2,4… uzunluk rank çiftlerini sıralar; radix sıralamalı varyant O(n log n) olabilir, comparison sort'lu aşamalar farklı sınır verir.

LCP komşu suffix'lerin ortak prefix uzunluğudur. Kasai algoritması önceki eşleşmeden en fazla bir karakter azaltarak toplam doğrusal tarama sağlar. Repeated substring ve distinct substring sayısı LCP üzerinden çıkar. Suffix tree sıkıştırılmış trie yapısıdır; linear construction mümkündür ama uygulaması ve edge-label sözleşmesi zordur.

BWT ve FM-index backward search ile sıkıştırılmış metin indeksleme yapar; rank/select yapıları önemlidir. “DNA'da göz kırpma süresi” diye sabit süre iddiası doğru değildir: pattern uzunluğu, output sayısı, disk/cache ve index türü belirleyicidir. Suffix automaton da substring state'lerini end-position eşdeğerliğine göre temsil eden ayrı güçlü bir yapıdır.

# Small-input oracle, NOT an efficient construction algorithm.
def suffix_array_oracle(text):
    return sorted(range(len(text)),key=lambda i:text[i:])
assert suffix_array_oracle("banana") == [5,3,1,0,4,2]