Dizeler
Desen eşleme ve palindromlar
KMP
Knuth-Morris-Pratt: bir uyumsuzluk metni asla yeniden taramasın diye en-uzun-önek-sonek tablosunu önceden hesaplar — doğrusal zamanda desen eşleme.
Süre O(n + m) · Alan O(m)
Rabin-Karp
Deseni ve her metin penceresini yuvarlanan bir hash ile hashler; yalnızca hash'ler çakıştığında karakter karakter doğrular.
Süre O(n + m) avg · Alan O(1)
Z-Algoritması
Her konum için, oradan başlayıp dizenin önekiyle eşleşen en uzun alt dizenin uzunluğunu hesaplar — bir [l, r) penceresini yeniden kullanarak.
Süre O(n) · Alan O(n)
Boyer-Moore
Deseni sağdan sola karşılaştırır ve kötü-karakter tablosuyla umutsuz hizalamaların üzerinden atlar — pratikte çoğu zaman alt-doğrusal.
Süre O(n/m) best · Alan O(σ)
Manacher Algoritması
Merkezler etrafında genişleyip yarıçapları mevcut palindrom boyunca yansıtarak en uzun palindrom alt dizeyi doğrusal zamanda bulur.
Süre O(n) · Alan O(n)