String Algoritmaları

Bir metin editöründe Ctrl+F'ye bastığında, grep ile log dosyalarında hata aradığında ya da bir biyoinformatik aracı milyonlarca harflik bir DNA dizisinde belirli bir geni bulduğunda aynı temel problem çözülür: desen eşleme (pattern matching). Kopya tespit sistemleri, virüs tarayıcıları ve arama motorları da farklı ölçeklerde aynı soruyla uğraşır: bu desen bu metnin neresinde geçiyor?

İlk akla gelen çözüm, deseni metnin her konumuna yerleştirip karakter karakter karşılaştırmaktır. Gündelik metinlerde bu genellikle yeterince hızlıdır, ama aaaa…ab gibi tekrarlı girdilerde O(n·m) zamana düşer. Bu derste bu yavaşlığı ortadan kaldıran üç klasik fikri öğreneceksin: KMP'nin önek fonksiyonu, Rabin-Karp'ın kayan hash'i ve Z algoritmasının Z-kutusu. Üçü de aynı gözleme dayanır: daha önce karşılaştırdığın karakterler hakkında öğrendiğin bilgiyi çöpe atma.

Ardından mülakatların gözdesi olan palindrom ve anagram problemlerine geçeceğiz. Hepsinin üzerinde Go'ya özgü bir soru var: string'i bayt dizisi olarak mı, rune dizisi olarak mı işlemeliyim? Türkçe metinlerde yanlış seçim ç, ş ve ı gibi harflerde sessizce yanlış sonuç üretir.

Dersin sonunda naif arama, KMP, Rabin-Karp ve Z algoritmasını sıfırdan yazabilecek ve karmaşıklıklarını gerekçesiyle açıklayabileceksin. Palindrom ve anagram problemlerini Türkçe karakterlerle doğru çözebilecek, pratikte ne zaman standart kütüphaneye güvenmen gerektiğini de bileceksin.

Go'da string'ler: bayt mı, rune mı?

String, Byte ve Rune dersinden hatırla: Go'da bir string, değiştirilemeyen bir bayt dizisidir ve kaynak kodundaki metinler UTF-8 ile kodlanır. len(s) bayt sayısını, s[i] i. baytı verir. Türkçe harflerin çoğu tek bayt olsa da ç, ğ, ı, İ, ö, ş ve ü ikişer bayt kaplar. Tek bir Unicode kod noktasını ise rune tipi (int32) temsil eder.

Bu yüzden her string algoritmasına başlamadan önce şu soruyu sormalısın: algoritmam karakterleri mi, baytları mı işliyor?

İlk satırdaki iddia UTF-8'in akıllıca tasarımından gelir: bir karakterin ilk baytı ile devam baytları farklı bit desenlerine sahiptir (devam baytları hep 10xxxxxx biçimindedir). Bu yüzden geçerli bir desen, metinde bir karakterin ortasından başlayarak eşleşemez. Arama algoritmalarını baytlar üzerinde yazmak Türkçe metinde de doğru sonuç verir; yalnızca dönen indeksin bayt indeksi olduğunu unutmamalısın.

package main

import (
	"fmt"
	"strings"
	"unicode/utf8"
)

func reverseBytes(s string) string {
	b := []byte(s)
	for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
		b[i], b[j] = b[j], b[i]
	}
	return string(b)
}

func reverseRunes(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

func main() {
	s := "çiçek"
	fmt.Println("bayt:", len(s), "rune:", utf8.RuneCountInString(s))
	fmt.Printf("s[0] = %d, 'ç' = %d\n", s[0], 'ç')
	fmt.Printf("bayt bayt ters: %q\n", reverseBytes(s))
	fmt.Printf("rune rune ters: %q\n", reverseRunes(s))

	i := strings.Index(s, "ek")
	fmt.Println("bayt indeksi:", i, "karakter indeksi:", utf8.RuneCountInString(s[:i]))
}

bayt: 7 rune: 5
s[0] = 195, 'ç' = 231
bayt bayt ters: "ke\xa7\xc3i\xa7\xc3"
rune rune ters: "keçiç"
bayt indeksi: 5 karakter indeksi: 3

Bayt bayt ters çevirmek ç harfinin iki baytını ters sıraya soktu ve geçersiz UTF-8 üretti; %q bu bozuk baytları \xa7\xc3 olarak gösteriyor. strings.Index ise doğru konumu buldu, ama 5 değeri bayt indeksidir; karakter olarak "ek" 3. konumdadır. Bu derste arama algoritmalarını baytlarla, palindrom ve anagramları rune'larla yazacağız.

Naif desen eşleme

n uzunluğundaki bir metinde m uzunluğundaki bir deseni aramanın en doğrudan yolu şudur: deseni metnin 0. konumuna hizala ve karakter karakter karşılaştır. Uyuşmazlık görürsen ya da desen biterse, deseni bir sağa kaydır ve baştan başla.

AABAACAADAABAABA metninde AABA desenini arayalım:

indeks:  0 1 2 3 4 5 6 7 8 9 ...
metin:   A A B A A C A A D A A B A A B A
i = 0:   A A B A                          ✓ eşleşme          (4 karşılaştırma)
i = 1:     A A                            ✗ B ≠ A            (2 karşılaştırma)
i = 2:       A                            ✗ B ≠ A            (1 karşılaştırma)
i = 3:         A A B                      ✗ C ≠ B            (3 karşılaştırma)
i = 4:           A A                      ✗ C ≠ A            (2 karşılaştırma)
...

i = 1 satırına dikkat: i = 0 hizalamasında metnin 1. ve 2. karakterlerinin A ve B olduğunu zaten öğrenmiştik. Naif algoritma bu bilgiyi unutup aynı karakterleri yeniden karşılaştırıyor. İlerideki algoritmaların hepsi bu israfı ortadan kaldırmak için tasarlandı.

package main

import (
	"fmt"
	"strings"
)

// naiveSearch, desenin metindeki bütün başlangıç indekslerini ve
// yapılan karakter karşılaştırması sayısını döndürür.
func naiveSearch(text, pattern string) ([]int, int) {
	n, m := len(text), len(pattern)
	var matches []int
	comparisons := 0
	for i := 0; i+m <= n; i++ {
		j := 0
		for j < m {
			comparisons++
			if text[i+j] != pattern[j] {
				break
			}
			j++
		}
		if j == m {
			matches = append(matches, i)
		}
	}
	return matches, comparisons
}

func main() {
	matches, cmp := naiveSearch("AABAACAADAABAABA", "AABA")
	fmt.Println("eşleşmeler:", matches, "karşılaştırma:", cmp)

	// En kötü durum: her hizalamada neredeyse tam eşleşme
	text := strings.Repeat("A", 1000)
	pattern := strings.Repeat("A", 99) + "B"
	matches, cmp = naiveSearch(text, pattern)
	fmt.Println("eşleşmeler:", matches, "karşılaştırma:", cmp)
}

eşleşmeler: [0 9 12] karşılaştırma: 30
eşleşmeler: [] karşılaştırma: 90100

İkinci örnekte 901 hizalamanın her birinde 100 karşılaştırma yapıldı: (n − m + 1) · m = 90.100. Metin bir milyon, desen bin karakter olsaydı bu yaklaşık bir milyar karşılaştırma ederdi. Rastgele metinlerde uyuşmazlık genellikle ilk bir iki karakterde bulunduğundan naif arama pratikte hızlı çalışır; sorun, garanti vermemesidir.

KMP ve önek fonksiyonu

Sezgi

Naif algoritma bir uyuşmazlıkta her şeyi unutur. Oysa uyuşmazlıktan önce eşleşen j karakteri zaten biliyoruz: onlar desenin ilk j karakterinin ta kendisidir. KMP (Knuth-Morris-Pratt) algoritması bu bilgiyi kullanır: metinde asla geri gitmez, yalnızca desendeki konumunu akıllıca geri çeker.

ABABABCABAB metninde ABABCABAB desenini ararken ne olduğuna bak:

indeks:  0 1 2 3 4 5 6 7 8 9 10
metin:   A B A B A B C A B A B
desen:   A B A B C                  i = 4'te uyuşmazlık: A ≠ C
                                    eşleşen kısım "ABAB"; sonundaki "AB" desenin başıyla aynı

desen:       A B A B C A B A B      deseni 2 kaydır: baştaki "AB" zaten eşleşmiş durumda
             ^ ^                    metinde geri gitmeden i = 4'ten devam et

Eşleşen ABAB parçasının hem başında hem sonunda AB var. Bu yüzden deseni, baştaki AB sondaki ABnin üzerine gelecek şekilde kaydırabilir ve karşılaştırmaya desenin 2. karakterinden devam edebiliriz. Bu "hem önek hem sonek olan en uzun parça" bilgisini her konum için önceden hesaplarsak, uyuşmazlıkta nereye döneceğimizi anında biliriz.

Önek fonksiyonu (LPS dizisi)

Bir string'in öz öneki (proper prefix), string'in tamamı hariç herhangi bir önekidir. LPS dizisi (longest proper prefix which is also suffix), önek fonksiyonu olarak da bilinir ve şöyle tanımlanır:

lps[i] = p[0..i] parçasının hem öz öneki hem soneki olan en uzun string'in uzunluğu.

ABABCABAB deseni için:

Örneğin lps[8] = 4, çünkü ABABCABAB parçası ABAB ile başlar ve ABAB ile biter; daha uzun bir ortak önek-sonek yoktur. lps[4] = 0 ise ABABC parçasının C ile bittiğini ve C ile başlayan bir öneki olmadığını söyler.

Diziyi O(m²) ile saf biçimde hesaplamak kolaydır, ama KMP'nin güzelliği LPS dizisini de kendi fikriyle O(m) zamanda hesaplamasıdır. k değişkeni, bir önceki konum için bulunan en uzun kenarın uzunluğunu tutar:

func buildLPS(p string) []int {
	lps := make([]int, len(p))
	k := 0 // bir önceki konumdaki en uzun kenarın uzunluğu
	for i := 1; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = lps[k-1] // bir sonraki daha kısa kenarı dene
		}
		if p[i] == p[k] {
			k++
		}
		lps[i] = k
	}
	return lps
}

Her adımda sorulan soru şudur: "Önceki kenarı p[i] ile bir karakter uzatabilir miyim?" Kenarın hemen ardındaki karakter p[k]'dir. Eşitse kenar bir uzar. Değilse daha kısa bir kenar denemek gerekir. Denenecek bir sonraki aday rastgele değildir: p[0..i-1] parçasının k'dan kısa her kenarı, aynı zamanda p[0..k-1] parçasının da bir kenarıdır. Bu yüzden bir sonraki aday lps[k-1] olur. ABABCABAB için adım adım:

Geri düşme zincirinin birden fazla adım sürdüğü bir örnek görmek için AAACAAAA desenine bak: son konumda k = 3 iken p[7] = A ≠ p[3] = C olur, k önce lps[2] = 2'ye düşer, ardından p[7] = A = p[2] olduğu için yeniden 3'e çıkar. Aşağıdaki programda bu desenin LPS dizisini de göreceksin.

KMP ile arama

Arama, LPS inşasıyla neredeyse aynı koddur; tek fark, desenin kendisiyle değil metinle karşılaştırma yapmamızdır. k, metnin şu anki konumunda desenin kaç karakterinin eşleşmiş olduğunu tutar. k desen uzunluğuna ulaştığında bir eşleşme bulmuşuzdur. Çakışan eşleşmeleri de bulmak için ardından sıfırdan değil lps[k-1] değerinden devam ederiz.

Yukarıdaki ABABABCABAB örneğinin tam izi:

package main

import "fmt"

func buildLPS(p string) []int {
	lps := make([]int, len(p))
	k := 0
	for i := 1; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = lps[k-1]
		}
		if p[i] == p[k] {
			k++
		}
		lps[i] = k
	}
	return lps
}

// kmpSearch, desenin metindeki bütün başlangıç indekslerini döndürür.
func kmpSearch(text, pattern string) []int {
	m := len(pattern)
	if m == 0 {
		return nil
	}
	lps := buildLPS(pattern)
	var matches []int
	k := 0 // desenin eşleşmiş karakter sayısı
	for i := 0; i < len(text); i++ {
		for k > 0 && text[i] != pattern[k] {
			k = lps[k-1]
		}
		if text[i] == pattern[k] {
			k++
		}
		if k == m {
			matches = append(matches, i-m+1)
			k = lps[k-1] // çakışan eşleşmeleri kaçırma
		}
	}
	return matches
}

func main() {
	for _, p := range []string{"ABABCABAB", "AAAA", "AAACAAAA", "ABCDE"} {
		fmt.Printf("%-10s lps = %v\n", p, buildLPS(p))
	}

	fmt.Println(kmpSearch("ABABABCABAB", "ABABCABAB"))
	fmt.Println(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"))
	fmt.Println(kmpSearch("AAAAA", "AA"))
	fmt.Println(kmpSearch("gitti gidiyor, gitmesin", "git"))
}

ABABCABAB  lps = [0 0 1 2 0 1 2 3 4]
AAAA       lps = [0 1 2 3]
AAACAAAA   lps = [0 1 2 0 1 2 3 3]
ABCDE      lps = [0 0 0 0 0]
[2]
[10]
[0 1 2 3]
[0 15]

Neden O(n + m)? İçteki for döngüsü korkutucu görünebilir, ama bir amortize analiz argümanı işi çözer. k, metnin her karakteri için en fazla 1 artar; toplam artış en fazla n'dir. İç döngünün her turu k'yı en az 1 azaltır ve k hiçbir zaman negatif olmaz. Hiçbir şey, toplamda eklenenden fazlasını çıkaramaz; dolayısıyla iç döngü bütün arama boyunca en fazla n kez döner. Aynı argüman LPS inşası için O(m) verir. Amortize analizin ayrıntıları için Karmaşıklık Analizi dersine bakabilirsin.

Rabin-Karp ve kayan hash

Sezgi: parmak izi karşılaştırmak

Rabin-Karp farklı bir yol izler: m karakterlik iki parçayı karakter karakter karşılaştırmak yerine önce parmak izlerini (hash değerlerini) karşılaştırır. Hash'ler farklıysa parçalar kesinlikle farklıdır. Hash'ler eşitse parçalar büyük olasılıkla aynıdır, ama emin olmak için gerçek bir karşılaştırma yaparız.

Bunun işe yaraması için bir sonraki pencerenin hash'ini O(1)'de hesaplayabilmemiz gerekir. Onluk sayılarla bir benzetme yapalım. Rakamlar üzerinde 3 genişliğinde bir pencere kaydırıyoruz:

rakamlar:   3 1 4 1 5 9
pencere 1:  3 1 4          → 314
pencere 2:    1 4 1        → (314 − 3·100) · 10 + 1 = 141
pencere 3:      4 1 5      → (141 − 1·100) · 10 + 5 = 415

Soldaki rakamın katkısını çıkar, kalanı bir basamak kaydır, yeni rakamı ekle. Bu, kayan pencere fikrinin sayılara uygulanmış halidir. Karakterler için taban olarak 10 yerine bir B sayısı (örneğin 256) kullanırız ve sayılar çok büyümesin diye her adımda büyük bir asal M ile mod alırız:

h(s[0..m-1]) = (s[0]·B^(m-1) + s[1]·B^(m-2) + … + s[m-1]·B^0) mod M

pencereyi bir sağa kaydır:
h' = ((h − s[i]·B^(m-1)) · B + s[i+m]) mod M

Go'da uint64 aritmetiği

Uygulamada dikkat etmen gereken üç ayrıntı var:

1. Taşma: M = 1.000.000.007 (2³⁰'dan küçük bir asal) seçersek, M'den küçük iki sayının çarpımı 2⁶⁰'ı geçmez ve uint64'e rahatça sığar. Her çarpmadan sonra mod al.
2. Eksiye düşme: uint64 ile h - out işleminde out > h ise sonuç sarmalar ve anlamsız büyük bir sayı olur. Çıkarmadan önce M ekle: (h + M - out) % M.
3. Doğrulama: Farklı iki parçanın hash'i eşit olabilir (çakışma). Hash eşleştiğinde parçaları mutlaka karşılaştır. Bunu atlarsan program bazen var olmayan eşleşmeler raporlar.

Aşağıdaki program aynı aramayı iki farklı modülle yapıyor. M = 13 gibi küçük bir modülde çakışmaların ne kadar sık olduğunu ve doğrulamanın onları nasıl elediğini göreceksin.

package main

import "fmt"

const base = 256

// rabinKarp, desenin başlangıç indekslerini ve hash'i eşleştiği hâlde
// metnin eşleşmediği (yanlış alarm) pencerelerin sayısını döndürür.
func rabinKarp(text, pattern string, mod uint64) ([]int, int) {
	n, m := len(text), len(pattern)
	if m == 0 || m > n {
		return nil, 0
	}

	// pow = base^(m-1) mod M: pencereden çıkan karakterin ağırlığı
	pow := uint64(1)
	for range m - 1 {
		pow = pow * base % mod
	}

	var hp, ht uint64
	for i := range m {
		hp = (hp*base + uint64(pattern[i])) % mod
		ht = (ht*base + uint64(text[i])) % mod
	}

	var matches []int
	spurious := 0
	for i := 0; i+m <= n; i++ {
		if i > 0 {
			// soldaki karakteri çıkar, sağdaki karakteri ekle
			out := uint64(text[i-1]) * pow % mod
			ht = (ht + mod - out) % mod
			ht = (ht*base + uint64(text[i+m-1])) % mod
		}
		if hp == ht {
			if text[i:i+m] == pattern { // çakışmaya karşı doğrula
				matches = append(matches, i)
			} else {
				spurious++
			}
		}
	}
	return matches, spurious
}

func main() {
	text := "GATTACAGATTACAGATTACA"
	for _, mod := range []uint64{1_000_000_007, 13} {
		matches, spurious := rabinKarp(text, "TACA", mod)
		fmt.Printf("M = %d: eşleşmeler %v, yanlış alarm %d\n", mod, matches, spurious)
	}
}

M = 1000000007: eşleşmeler [3 10 17], yanlış alarm 0
M = 13: eşleşmeler [3 10 17], yanlış alarm 2

Her iki durumda da sonuç doğru, çünkü her hash eşleşmesini doğruladık. Küçük modülde ise bazı pencereler boşuna karşılaştırıldı. Büyük bir asal modülde, "rastgele gibi davranan" girdiler için tek bir pencerenin yanlış alarm verme olasılığı kabaca 1/M civarındadır. Ancak B ve M sabitse, algoritmayı bilen biri çakışan girdiler üretebilir. Güvenilmeyen girdilerde tabanı çalışma zamanında rastgele seç ya da iki farklı modülle iki hash tut.

En kötü durum, çok sayıda hash eşleşmesinin doğrulanması gerektiğinde ortaya çıkar. Örneğin AAAA…A metninde AA aradığında her pencere gerçek bir eşleşmedir ve her biri O(m) ile doğrulanır.

Birden çok deseni aynı anda aramak

Rabin-Karp'ın asıl parladığı yer çoklu desen aramasıdır. Aynı uzunlukta k desen arıyorsan, her desenin hash'ini bir map'e koy ve metnin üzerinden bir kez kaydır. Her pencerede tek bir map sorgusu, o hash'e sahip bir desen olup olmadığını söyler. KMP ile aynı iş için metni k kez taraman gerekirdi.

package main

import "fmt"

const (
	base = 256
	mod  = 1_000_000_007
)

func hashOf(s string) uint64 {
	var h uint64
	for i := range len(s) {
		h = (h*base + uint64(s[i])) % mod
	}
	return h
}

// searchAll, aynı uzunluktaki bütün desenleri metinde tek geçişte arar.
func searchAll(text string, patterns []string) {
	m := len(patterns[0])
	byHash := make(map[uint64][]string)
	for _, p := range patterns {
		h := hashOf(p)
		byHash[h] = append(byHash[h], p)
	}

	pow := uint64(1)
	for range m - 1 {
		pow = pow * base % mod
	}

	h := hashOf(text[:m])
	for i := 0; i+m <= len(text); i++ {
		if i > 0 {
			h = (h + mod - uint64(text[i-1])*pow%mod) % mod
			h = (h*base + uint64(text[i+m-1])) % mod
		}
		for _, p := range byHash[h] {
			if text[i:i+m] == p {
				fmt.Printf("%2d: %s\n", i, p)
			}
		}
	}
}

func main() {
	searchAll("ACGTTGCAACGTACGGTT", []string{"ACG", "GTT", "CAA"})
}

 0: ACG
 2: GTT
 6: CAA
 8: ACG
12: ACG
15: GTT

Map'ten okuduğumuz halde çıktı sırası deterministiktir, çünkü metni soldan sağa geziyoruz ve map'in üzerinde değil, tek bir anahtarın dilimi üzerinde dönüyoruz. Beklenen maliyet O(n + k·m) olur. Desenler farklı uzunluktaysa onları uzunluğa göre gruplayıp her uzunluk için ayrı bir tarama yapabilirsin. Çok sayıda farklı uzunlukta desen için ise trie üzerine KMP'nin geri düşme bağlantılarını ekleyen Aho-Corasick otomatı standart çözümdür.

Z algoritması

Z dizisi

Z algoritması tek bir diziyle çalışır ve çoğu kişiye KMP'den daha sezgisel gelir. s string'i için:

Z[i] = s ile s[i:] parçasının ortak en uzun önekinin uzunluğu.

Yani Z[i], i konumundan başlayarak string'in başıyla kaç karakter boyunca eşleştiğini söyler. Z[0] tanım gereği bütün string olurdu; kural olarak 0 kabul edilir. aabcaabxaaaz için:

Z[4] = 3 çünkü 4. konumdan başlayan aabx… ile string'in başı aabc… ilk üç karakterde (aab) aynı, dördüncüde farklıdır.

Z-kutusu ile O(n)

Her Z[i]'yi baştan karşılaştırarak hesaplamak O(n²) sürer. Z algoritması, şimdiye kadar bulunan ve en sağa uzanan eşleşme aralığını [l, r) olarak saklar. Bu aralığa Z-kutusu denir: s[l:r], string'in s[0:r-l] önekiyle birebir aynıdır.

indeks:   0 1 2 3 4 5 6 7
s:        a a b c a a b x ...
                  └─────┘
                  l=4   r=7     s[4:7] = "aab" = s[0:3]   (Z-kutusu)

i = 5 kutunun içinde. Kutu, s[0:3]'ün bir kopyası olduğundan
s[5:7] = s[1:3] olduğunu biliyoruz. Bu yüzden:
    Z[5] ≥ min(Z[5−4], r − 5) = min(Z[1], 2) = min(1, 2) = 1
Z[1] = 1 < 2 olduğu için Z[5] tam olarak 1'dir; karşılaştırmaya gerek yok.

Kural şu: i kutunun içindeyse (i < r), Z[i] en az min(Z[i-l], r-i) olur, çünkü kutu içindeki her şey önekteki karşılığının kopyasıdır. Bu başlangıç değerinden sonra karakterleri doğrudan karşılaştırarak genişletmeye devam ederiz; genişleme kutunun sağ sınırını geçerse kutuyu güncelleriz. Her başarılı karşılaştırma r'yi bir ileri iter ve r hiç geri gitmez; bu yüzden toplam karşılaştırma sayısı O(n)'dir.

Z ile desen eşleme

Deseni metinde aramak için pattern + "$" + text string'inin Z dizisini hesapla. Burada $, ne desende ne de metinde geçmeyen bir ayırıcıdır. Birleşik string'de Z[i] == m olan her konum, metnin i - m - 1 indeksinde bir eşleşme demektir. Ayırıcı sayesinde hiçbir Z değeri m'yi aşamaz.

package main

import "fmt"

func zFunction(s string) []int {
	n := len(s)
	z := make([]int, n)
	l, r := 0, 0 // [l, r): s'nin bir önekiyle eşleşen en sağdaki aralık
	for i := 1; i < n; i++ {
		if i < r {
			z[i] = min(r-i, z[i-l]) // kutudaki bilgiyi yeniden kullan
		}
		for i+z[i] < n && s[z[i]] == s[i+z[i]] {
			z[i]++
		}
		if i+z[i] > r {
			l, r = i, i+z[i]
		}
	}
	return z
}

func zSearch(text, pattern string) []int {
	m := len(pattern)
	if m == 0 {
		return nil
	}
	z := zFunction(pattern + "$" + text)
	var matches []int
	for i := m + 1; i < len(z); i++ {
		if z[i] == m {
			matches = append(matches, i-m-1)
		}
	}
	return matches
}

func main() {
	fmt.Println(zFunction("aabcaabxaaaz"))
	fmt.Println(zFunction("aab$aabxaabaab"))
	fmt.Println(zSearch("aabxaabaab", "aab"))
	fmt.Println(zSearch("ABABDABACDABABCABAB", "ABABCABAB"))
}

[0 1 0 0 3 1 0 0 2 2 1 0]
[0 1 0 0 3 1 0 0 3 1 0 3 1 0]
[0 4 7]
[10]

İkinci satır birleşik string'in Z dizisi: 4, 8 ve 11. konumlarda 3 (desen uzunluğu) değeri var; bunlardan 4 çıkarınca metindeki 0, 4 ve 7 indekslerini buluyoruz.

Hangi algoritma ne zaman?

Bu algoritmaları bilmek mülakatlarda, standart kütüphanenin yetmediği problemlerde (çoklu desen, akış halinde gelen veri, önek fonksiyonunun kendisinin gerektiği sorular) ve karmaşıklık analizinde işine yarar. Ama tek bir alt string arıyorsan strings.Index, strings.Contains, strings.Count veya bytes.Index kullan. Standart kütüphanenin uygulaması yüksek düzeyde optimize edilmiştir. Go 1.26 kaynak koduna bakarsan tek baytlık desenler için ayrı bir hızlı yol, kısa desenler için platforma özel karşılaştırma rutinleri ve çok fazla yanlış aday çıktığında Rabin-Karp'a geçen bir strateji görürsün. Bu ayrıntılar sürümden sürüme değişebilir. Kendi yazdığın bir aramayı standart kütüphaneye tercih etmeyi düşünüyorsan önce benchmark ile ölç.

Palindromlar

Tersten okunuşu düzünden okunuşuyla aynı olan string'e palindrom denir: kabak, ütü, kelek. Türkçenin meşhur palindrom cümlesi "Ey Edip, Adana'da pide ye" de noktalama ve büyük harfler yok sayıldığında bir palindromdur.

Merkezden genişleme

"En uzun palindromik alt string" problemini düşün. Kaba kuvvet bütün O(n²) alt string'i üretir ve her birini O(n)'de kontrol eder: O(n³). Daha iyi bir fikir, her palindromun bir merkezi olduğunu fark etmektir. Merkezden iki yana doğru, karakterler eşit olduğu sürece genişleyebiliriz.

İki tür merkez vardır: tek uzunluklu palindromların merkezi bir karakterdir (kabak'taki b), çift uzunlukluların merkezi iki karakterin arasıdır (abba'daki bb arası). n karakterlik bir string'de n tane tek ve n − 1 tane çift merkez, toplam 2n − 1 merkez vardır. Her merkezden genişleme en fazla O(n) sürdüğünden toplam O(n²) olur.

rune indeksi:  4  5  6  7  8  9  10
rune:          k  e  ç  i  ç  e  k        ("kelekeçiçek" string'inin bir parçası)
                        ^                 merkez 7
                     ç  =  ç              (6, 8) eşit → genişle
                  e  =     =  e           (5, 9) eşit → genişle
               k  =           =  k        (4, 10) eşit → genişle
                                          (3, 11): 11 dizinin dışında → dur
sonuç: [4, 11) aralığı → "keçiçek", uzunluk 7

Karakterleri karşılaştırdığımız için string'i önce []rune dilimine çeviriyoruz. Program ayrıca aynı palindrom kontrolünün baytlar üzerinde neden yanlış sonuç verdiğini de gösteriyor.

package main

import "fmt"

// expand, merkezden iki yana genişler ve palindromun [left, right) aralığını döndürür.
func expand(r []rune, left, right int) (int, int) {
	for left >= 0 && right < len(r) && r[left] == r[right] {
		left--
		right++
	}
	return left + 1, right
}

func longestPalindrome(s string) string {
	r := []rune(s) // dönüşümü bir kez yap
	bestL, bestR := 0, 0
	for c := range r {
		l1, r1 := expand(r, c, c)   // tek uzunluk: merkez bir karakter
		l2, r2 := expand(r, c, c+1) // çift uzunluk: merkez iki karakterin arası
		if r1-l1 > bestR-bestL {
			bestL, bestR = l1, r1
		}
		if r2-l2 > bestR-bestL {
			bestL, bestR = l2, r2
		}
	}
	return string(r[bestL:bestR])
}

func isPalindromeBytes(s string) bool {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

func main() {
	for _, s := range []string{"babad", "cbbd", "kelekeçiçek", "a", ""} {
		fmt.Printf("%q → %q\n", s, longestPalindrome(s))
	}

	fmt.Println("bayt ile \"çiç\" palindrom mu?", isPalindromeBytes("çiç"))
	fmt.Println("rune ile \"çiç\" palindrom mu?", longestPalindrome("çiç") == "çiç")
}

"babad" → "bab"
"cbbd" → "bb"
"kelekeçiçek" → "keçiçek"
"a" → "a"
"" → ""
bayt ile "çiç" palindrom mu? false
rune ile "çiç" palindrom mu? true

çiç baytlarla C3 A7 69 C3 A7 şeklindedir; tersi A7 C3 69 A7 C3 olur ve ilk bayt ile son bayt farklıdır. Harf düzeyinde kusursuz bir palindrom, bayt düzeyinde palindrom değildir. cbbd örneği ise çift merkezleri neden ayrıca denememiz gerektiğini gösteriyor: yalnızca tek merkezlere bakan bir çözüm bb yerine tek harflik bir sonuç döndürürdü.

Alan O(n), []rune dönüşümünden gelir; yalnızca ASCII metin işliyorsan doğrudan baytlarla çalışarak ek alanı O(1)'e indirebilirsin.

Manacher algoritması

Merkezden genişleme mülakatların neredeyse tamamı için yeterlidir. Ama n 10⁵ ve üzerindeyse O(n²) yetmez. Manacher algoritması aynı problemi O(n) zamanda çözer. Fikri Z algoritmasına çok benzer: şimdiye kadar bulunan ve en sağa uzanan palindromu saklar. Bu palindromun içindeki bir merkezin yarıçapı, palindromun merkezine göre ayna simetriği olan konumdaki yarıçaptan başlatılır ve yalnızca sınırın ötesi karşılaştırılır. Tek ve çift uzunlukları tek bir döngüde ele almak için karakterlerin arasına ayırıcı eklenir (abba → #a#b#b#a#). Uygulaması ince ayrıntılar içerdiğinden burada kodlamıyoruz; merkezden genişlemeyi iyice anladıysan Manacher'i okumak kolay olacaktır.

Anagramlar

İki string aynı harflerden aynı sayıda içeriyorsa birbirinin anagramıdır: kitap ile katip, kazık ile kızak, ışık ile kışı.

Sayma ile anagram kontrolü

İki yol var. Birincisi, iki string'in rune'larını sıralayıp karşılaştırmaktır: O(k log k). İkincisi harfleri saymaktır: bir string'in harflerinde sayacı artır, diğerininkinde azalt; sonunda bütün sayaçlar sıfırsa iki string anagramdır. Bu yol O(k) sürer.

Alfabe yalnızca a–z ise sayaç olarak [26]int dizisi yeterlidir. Türkçe metinde ise map[rune]int kullanırız. "Baytları sayarım, UTF-8 zaten doğru çalışır" diye düşünme; iki farklı harf kümesi aynı bayt kümesine sahip olabilir. Aşağıdaki programın son satırı tam olarak bunu gösteriyor: ç (C3 A7) ve ğ (C4 9F) ile ß (C3 9F) ve ħ (C4 A7) aynı dört baytın farklı eşleşmeleridir.

package main

import (
	"fmt"
	"strings"
	"unicode"
)

// isAnagram, iki metnin aynı harfleri aynı sayıda içerip içermediğini söyler.
// Harf olmayan karakterleri yok sayar, Türkçe kurallarıyla küçük harfe çevirir.
func isAnagram(a, b string) bool {
	counts := make(map[rune]int)
	for _, r := range strings.ToLowerSpecial(unicode.TurkishCase, a) {
		if unicode.IsLetter(r) {
			counts[r]++
		}
	}
	for _, r := range strings.ToLowerSpecial(unicode.TurkishCase, b) {
		if unicode.IsLetter(r) {
			counts[r]--
		}
	}
	for _, c := range counts {
		if c != 0 {
			return false
		}
	}
	return true
}

// sameBytes yalnızca bayt sıklıklarını karşılaştırır: Unicode için YANLIŞ.
func sameBytes(a, b string) bool {
	var counts [256]int
	for i := range len(a) {
		counts[a[i]]++
	}
	for i := range len(b) {
		counts[b[i]]--
	}
	return counts == [256]int{}
}

func main() {
	fmt.Println(isAnagram("kazık", "kızak"))
	fmt.Println(isAnagram("KİTAP", "katip"))
	fmt.Println(isAnagram("kalem", "melek"))

	fmt.Println(strings.ToLower("Işık"), strings.ToLowerSpecial(unicode.TurkishCase, "Işık"))
	fmt.Println(isAnagram("Işık", "kışı"))

	fmt.Println("bayt sayımı:", sameBytes("çğ", "ßħ"), "| rune sayımı:", isAnagram("çğ", "ßħ"))
}

true
true
false
işık ışık
true
bayt sayımı: true | rune sayımı: false

Dördüncü satır Türkçenin klasik tuzağını gösteriyor: strings.ToLower büyük I harfini i'ye çevirir ve Işık kelimesini işık yapar. unicode.TurkishCase ile ise doğru sonuç olan ışık elde edilir. KİTAP örneğinde de İ harfinin Türkçe kurallarla i'ye dönüştüğünü görüyorsun.

Anagram gruplama

Problem: Bir kelime listesini, birbirinin anagramı olan kelimeler aynı grupta olacak şekilde grupla.

Anahtar fikir, her anagram grubunun ortak bir imzası olmasıdır: kelimenin harfleri sıralandığında hepsi aynı string'e dönüşür (kazık ve kızak için akkzı). Bu imzayı map anahtarı yaparız. Sıralama rune'ların Unicode kod noktası değerine göre yapılır, bu yüzden ı (U+0131) z'den sonra gelir. Bu, Türkçe alfabe sırası değildir ama imza için önemli değildir; tek şart, aynı harf kümesinin hep aynı imzayı üretmesidir.

Map'in gezinme sırası rastgele olduğu için grupları map'ten doğrudan yazdırırsak çıktı her çalıştırmada değişebilir. Grupların ilk görülme sırasını ayrı bir dilimde tutarak deterministik bir çıktı elde ederiz.

package main

import (
	"fmt"
	"slices"
)

func groupAnagrams(words []string) [][]string {
	groups := make(map[string][]string)
	var order []string // imzaların ilk görülme sırası
	for _, w := range words {
		r := []rune(w)
		slices.Sort(r)
		key := string(r)
		if _, ok := groups[key]; !ok {
			order = append(order, key)
		}
		groups[key] = append(groups[key], w)
	}

	result := make([][]string, 0, len(order))
	for _, key := range order {
		result = append(result, groups[key])
	}
	return result
}

func main() {
	words := []string{"kitap", "elma", "kazık", "katip", "alem", "ışık", "kızak", "masa", "kışı", "asma", "kalem"}
	for _, group := range groupAnagrams(words) {
		fmt.Println(group)
	}
}

[kitap katip]
[elma alem]
[kazık kızak]
[ışık kışı]
[masa asma]
[kalem]

N kelime ve en uzun kelime uzunluğu k için her imza O(k log k)'da hesaplanır: toplam O(N · k log k) zaman, O(N · k) alan. Alfabe küçük ve sabitse sıralamak yerine harf sayılarını da imza yapabilirsin. Go'da diziler karşılaştırılabilir olduğu için map[[26]int][]string gibi bir map geçerlidir ve imza O(k)'da hesaplanır. Map'lerin iç yapısını merak ediyorsan Hash Tabloları dersine göz at.

Türkçe metinlerde rune dikkatleri

Buraya kadar gördüğümüz tuzakları ve birkaç yenisini bir arada toplayalım.

Bayt indeksi karakter indeksi değildir. strings.Index, len ve s[i] baytlarla çalışır. Kullanıcıya "5. karakter" demen gerekiyorsa utf8.RuneCountInString(s[:i]) ile dönüştür. Bir string'i baştan sona gezmek için []rune dönüşümü yerine for i, r := range s kullanabilirsin; bu döngü rune'ları çözerken bellek ayırmaz. []rune dönüşümü ise her rune için 4 bayt ayırır; rastgele erişim gerekiyorsa buna değer.

Büyük/küçük harf dönüşümü dile bağlıdır. strings.ToUpper("istanbul") sonucu ISTANBUL'dur; Türkçe için doğru olan İSTANBUL sonucunu strings.ToUpperSpecial(unicode.TurkishCase, s) verir. strings.EqualFold("ı", "I") da false döner. Büyük/küçük harf duyarsız karşılaştırma yapacaksan iki tarafı da Türkçe kurallarla aynı biçime getirip öyle karşılaştır.

Aynı görünen iki string farklı olabilir. Unicode'da é harfi tek bir kod noktası (U+00E9) olarak da, e harfi ile birleşen vurgu işareti (U+0301) çifti olarak da yazılabilir. Ekranda birebir aynı görünürler, ama baytları, rune sayıları ve == sonuçları farklıdır. macOS dosya sistemlerinden, kopyala-yapıştırdan veya farklı klavyelerden gelen metinlerde bu durumla karşılaşabilirsin.

package main

import (
	"fmt"
	"strings"
	"unicode/utf8"
)

func main() {
	composed := "café"    // é tek kod noktası
	decomposed := "café" // e + birleşen vurgu işareti

	fmt.Println("eşit mi?", composed == decomposed)
	fmt.Println("bayt:", len(composed), len(decomposed))
	fmt.Println("rune:", utf8.RuneCountInString(composed), utf8.RuneCountInString(decomposed))
	fmt.Printf("%+q %+q\n", composed, decomposed)
	fmt.Println("içeriyor mu?", strings.Contains(decomposed, "é"))

	flag := "\U0001F1F9\U0001F1F7" // Türkiye bayrağı emojisi
	fmt.Println("bayrak emojisindeki rune sayısı:", utf8.RuneCountInString(flag))
}

eşit mi? false
bayt: 5 6
rune: 4 5
"caf\u00e9" "cafe\u0301"
içeriyor mu? false
bayrak emojisindeki rune sayısı: 2

Bu tür metinleri karşılaştırmadan önce aynı normal forma getirmek gerekir. Standart kütüphanede bunun için bir paket yoktur; Go ekibinin bakımını yaptığı golang.org/x/text/unicode/norm paketi kullanılır. Modüle eklemen gereken harici bir bağımlılık olduğu için aşağıdaki parça çalıştırılabilir değildir:

// go get golang.org/x/text
import "golang.org/x/text/unicode/norm"

a := norm.NFC.String(composed)   // birleşik biçime getir
b := norm.NFC.String(decomposed) // birleşik biçime getir
fmt.Println(a == b)              // true

Son satır da ayrı bir uyarı taşıyor: bayrak emojisi ekranda tek bir simge olsa da iki rune'dan oluşur. Kullanıcının gördüğü "harflere" grafem kümesi (grapheme cluster) denir ve rune'lar da bu anlamda her zaman "karakter" değildir. Tek bir kod noktasından oluşan Türkçe harflerle çalışırken rune yeterlidir; emoji veya birleşen işaretler içeren metinlerde ise grafem kümelerini ayıran bir kütüphaneye ihtiyaç duyarsın.

Sık yapılan hatalar

• Bayt indeksini karakter indeksi sanmak. strings.Index("çiçek", "ek") 3 değil 5 döndürür. Karakter konumu gerekiyorsa rune sayısına çevir.
• String'i bayt bayt ters çevirmek ya da palindrom kontrolünü baytlarla yapmak. Çok baytlı harfler bozulur; çiç palindrom olmaktan çıkar. Karakter düzeyindeki işlemler için []rune kullan.
• Türkçe metinde strings.ToLower veya strings.ToUpper kullanmak. I → i ve i → I dönüşümleri Türkçe için yanlıştır; unicode.TurkishCase kullan.
• Rabin-Karp'ta hash eşleşmesini doğrulamamak. Çakışmalar nadir de olsa gerçektir; doğrulamasız bir çözüm bazen var olmayan eşleşme raporlar.
• uint64 ile çıkarmadan önce modülü eklememek. (h - out) % M işlemi out > h olduğunda sarmalar. (h + M - out) % M yaz ve her çarpmadan sonra mod al.
• KMP'de tam eşleşmeden sonra k'yı sıfırlamak. k = 0 çakışan eşleşmeleri kaçırır (AAAAA içinde AA için yalnızca 0 ve 2 bulunur); k = lps[k-1] kullan.
• LPS inşasında geri düşmeyi tek bir if ile yapmak. Geri düşme zinciri birden fazla adım sürebilir (AAACAAAA); for döngüsü şarttır.
• Z aramasında girdide geçebilecek bir ayırıcı seçmek. Ayırıcı metinde varsa Z değerleri desen uzunluğunu aşar ve eşleşmeler yanlış raporlanır.
• Boş deseni düşünmemek. strings.Index(s, "") 0 döndürür; kendi fonksiyonunda boş desenin anlamını açıkça belirle ve lps[k-1] gibi erişimlerin panik üretmediğinden emin ol.
• Anagram gruplarını doğrudan map'ten yazdırmak. Map gezinme sırası rastgeledir; sıra gerekiyorsa anahtarları ayrıca tut ya da sırala.
• Merkezden genişlemede her merkez için []rune(s) dönüşümünü tekrarlamak. Dönüşüm O(n) sürer; döngünün dışında bir kez yap.

Alıştırmalar

package main

import (
	"fmt"
	"unicode"
)

func isSentencePalindrome(s string) bool {
	r := []rune(s)
	i, j := 0, len(r)-1
	for i < j {
		if !unicode.IsLetter(r[i]) && !unicode.IsDigit(r[i]) {
			i++
			continue
		}
		if !unicode.IsLetter(r[j]) && !unicode.IsDigit(r[j]) {
			j--
			continue
		}
		if unicode.TurkishCase.ToLower(r[i]) != unicode.TurkishCase.ToLower(r[j]) {
			return false
		}
		i++
		j--
	}
	return true
}

func main() {
	fmt.Println(isSentencePalindrome("Ey Edip, Adana'da pide ye"))
	fmt.Println(isSentencePalindrome("KILIK kılık"))
	fmt.Println(isSentencePalindrome("Ütü!"))
	fmt.Println(isSentencePalindrome("Kitap kaptı"))
	fmt.Println(isSentencePalindrome(""))
}

true
true
true
false
true

package main

import "fmt"

func findAnagram(pattern, text string) int {
	m, n := len(pattern), len(text)
	if m == 0 || m > n {
		return -1
	}
	var need, window [26]int
	for i := range m {
		need[pattern[i]-'a']++
		window[text[i]-'a']++
	}
	if need == window {
		return 0
	}
	for i := m; i < n; i++ {
		window[text[i]-'a']++   // sağdan giren harf
		window[text[i-m]-'a']-- // soldan çıkan harf
		if need == window {
			return i - m + 1
		}
	}
	return -1
}

func main() {
	fmt.Println(findAnagram("ab", "eidbaooo"))
	fmt.Println(findAnagram("ab", "eidboaoo"))
	fmt.Println(findAnagram("adc", "dcda"))
	fmt.Println(findAnagram("abc", "ab"))
}

3
-1
1
-1

package main

import "fmt"

func buildLPS(p string) []int {
	lps := make([]int, len(p))
	k := 0
	for i := 1; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = lps[k-1]
		}
		if p[i] == p[k] {
			k++
		}
		lps[i] = k
	}
	return lps
}

func repeatedPattern(s string) (string, bool) {
	n := len(s)
	if n == 0 {
		return "", false
	}
	border := buildLPS(s)[n-1]
	period := n - border
	if border > 0 && n%period == 0 {
		return s[:period], true
	}
	return "", false
}

func main() {
	for _, s := range []string{"abab", "aba", "abcabcabcabc", "abcab", "aaaa", "a"} {
		block, ok := repeatedPattern(s)
		fmt.Printf("%-14q %-6q %v\n", s, block, ok)
	}
}

"abab"         "ab"   true
"aba"          ""     false
"abcabcabcabc" "abc"  true
"abcab"        ""     false
"aaaa"         "a"    true
"a"            ""     false

package main

import "fmt"

const (
	base = 131
	mod  = 1_000_000_007
)

// findRepeat, L uzunluğunda en az iki kez geçen bir alt string'in
// ikinci geçişinin başlangıcını döndürür; yoksa -1.
func findRepeat(s string, L int) int {
	pow := uint64(1)
	for range L - 1 {
		pow = pow * base % mod
	}
	var h uint64
	for i := range L {
		h = (h*base + uint64(s[i])) % mod
	}
	seen := map[uint64][]int{h: {0}}
	for i := 1; i+L <= len(s); i++ {
		h = (h + mod - uint64(s[i-1])*pow%mod) % mod
		h = (h*base + uint64(s[i+L-1])) % mod
		for _, j := range seen[h] {
			if s[j:j+L] == s[i:i+L] { // çakışmaya karşı doğrula
				return i
			}
		}
		seen[h] = append(seen[h], i)
	}
	return -1
}

func longestDupSubstring(s string) string {
	best := ""
	lo, hi := 1, len(s)-1 // olası cevap uzunlukları
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if i := findRepeat(s, mid); i >= 0 {
			best = s[i : i+mid]
			lo = mid + 1 // daha uzununu dene
		} else {
			hi = mid - 1
		}
	}
	return best
}

func main() {
	for _, s := range []string{"banana", "abcd", "aabcaabdaab", "aaaaa", ""} {
		fmt.Printf("%q → %q\n", s, longestDupSubstring(s))
	}
}

"banana" → "ana"
"abcd" → ""
"aabcaabdaab" → "aab"
"aaaaa" → "aaaa"
"" → ""

Kısa sınav

Özet

• Go'da string bir bayt dizisidir. Alt string aramasını baytlarla yapmak geçerli UTF-8'de doğrudur ama bayt indeksi döndürür; ters çevirme, palindrom, sayma ve anagram gibi karakter düzeyindeki işler için []rune kullan.
• Naif arama basittir ama en kötü durumda O(n·m) sürer, çünkü her hizalamada öğrendiği bilgiyi unutur.
• KMP, her konum için "hem önek hem sonek olan en uzun parçayı" (LPS) önceden hesaplar ve metinde hiç geri gitmeden O(n + m)'de arar; çakışan eşleşmeler için k = lps[k-1] ile devam eder.
• Rabin-Karp pencere hash'ini O(1)'de kaydırır. Asal modül, çıkarmadan önce modül ekleme ve her hash eşleşmesini doğrulama şarttır. Çoklu desen ve "tekrarlanan alt string" problemlerinde çok güçlüdür.
• Z algoritması, Z-kutusundaki bilgiyi yeniden kullanarak her konumun önekle ortak uzunluğunu O(n)'de bulur; pattern + ayırıcı + text hilesiyle desen arar.
• Palindromlar için 2n − 1 merkezden genişleme O(n²) sürer; O(n) gerekiyorsa Manacher algoritması vardır.
• Anagramlar için harf sayımı (Türkçede map[rune]int) ve sıralı rune imzası kullanılır; grupları deterministik yazdırmak için sırayı ayrıca tut.
• Türkçe metinde unicode.TurkishCase kullan, Unicode normalizasyonuna ve grafem kümelerine dikkat et. Pratikte tek desen aramak için yüksek düzeyde optimize edilmiş strings.Index ailesini tercih et.