Longest Common Substring

Longest Common Substring, Longest Common Subsequence ile aynı problem değildir. Burada eşleşen karakterlerin her iki girdide de ardışık kalması gerekir; bu ayrım diff, içerik benzerliği ve biyolojik dizi işleme gibi işlerde sonucu doğrudan değiştirir.

Uygulama Notu

Klasik dinamik programlama çözümü O(m*n) zamanda çalışır ve yalnız önceki satır tutulursa bellek O(min(m,n)) düzeyine indirilebilir. Büyük corpus üzerinde tek sorgu yerine tekrar eden aramalar yapılacaksa suffix tree, suffix array veya suffix automaton tabanlı indeksleme daha anlamlı hale gelir.

En uzun eşleşmenin kendisi gerekiyorsa yalnız skor tutmak yetmez; bitiş konumu veya geri izleme bilgisi de korunmalıdır.

İlgili Kavramlar

• Edit Distance
• Suffix Array
• Suffix Automaton
• Dynamic Programming