KMP / String Matching

Nasıl düşünülür

Naif eşleştirme O(n*m)’dir: her konumda patterni karşılaştır, uyumsuzlukta geri dön. KMP geri dönüşü longest-prefix-suffix (LPS) dizisi ile ortadan kaldırır: lps[i], patternin pattern[0..i] sonekuyla aynı olan en uzun proper önekidir. j konumunda uyumsuzlukta, yeniden başlatmak yerine j’yi lps[j-1]’e atla, o kadar karakteri zaten eşleştin. LPS dizisini bir kez kur (O(m)), sonra metni bir tara (O(n)).

Rabin-Karp farklı bir yol izler: patterni hash’le, sonra metin boyunca hash’i kaydır. Rolling hash O(1)’de güncellenir (çıkan karakteri çıkar, base ile çarp, giren karakteri ekle, mod al). Hash patternin hash’ine eşit olduğunda, çakışmayı ekarte etmek için karakter karakter doğrula. Çoklu pattern eşleştirmede (hash set) veya metin akışında parlar.

Şablon şekilleri

Şekil	Temel hamle	Örnek
KMP tam eşleştirme	LPS kur; metni atlama ile tara	LC 28
En kısa palindrom	pattern + reverse(pattern)’in LPS’i	LC 214
En uzun mutlu önek	Stringin kendisinin LPS’i	LC 1392
Rabin-Karp rolling hash	Pattern hash’le; metinde hash kaydır	LC 3036

Karmaşıklık temeli

KMP: O(n + m) zaman, O(m) alan (LPS). Rabin-Karp: ortalama O(n + m), worst case O(n*m) (çok çakışma); double hash ile çakışmaları ihmal edilebilir yap. Rolling hash güncelleme: O(1).

Şablondan probleme

1. Tek pattern tam eşleştirme mi? → KMP. Çoklu pattern veya kayan? → Rabin-Karp.
2. LPS dizisini dikkatli kur, lps[i] i’den önceki önek uzunluğudur, i’dekinin değil.
3. Rabin-Karp için alfabeden büyük bir base ve büyük asal seç; her adımda mod al.
4. Hash eşleşmesini döndürmeden önce her zaman karakter kontrolüyle doğrula.

/** KMP template: build LPS array and find pattern in text. */

export function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let len = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) len = lps[len - 1]!;
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  return lps;
}

export function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;
  const lps = buildLps(pattern);
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}

/** KMP template: build LPS array and find pattern in text. */

export function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let len = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) len = lps[len - 1]!;
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  return lps;
}

export function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;
  const lps = buildLps(pattern);
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - j + 1;
  }
  return -1;
}