Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Find the Index of the First Occurrence in a String

Problem (yeniden ifade)

needle’ın haystack’te ilk geçtiği indeksi döndür; yoksa -1. Boş needle → 0.

Sezgi

Naif tarama O(n·m). KMP, needle’ın LPS dizisini önceden hesaplar; uyuşmazlıkta metni geri sarmadan en uzun uygun öneke zıplar.

Yaklaşımlar

KMP

Doğrulanmadı

Zaman O(n+m)Alan O(m)

Fikir. Needle için lps kur. Haystack’i j ile tara; uyuşmazlıkta j = lps[j-1]. j == m olunca i - m + 1 döndür.

Yürüyüş. sadbutsad / sad → 0. leetcode / leeto → -1.

Trade-off. Şablon. Kütüphane aramasına izin varsa indexOf yeter; “built-in yok, O(n+m)” isterlerse KMP.

Çözüm

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

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

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

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

Şablon bağlantısı

KMP tam eşleşme. LC 1392 string’in kendi LPS’si; LC 214 s + # + reverse(s) LPS’si.

Yansıma

pi[i] en uzun proper önek-sonek. Eşleşme bozulunca deseni pi kadar geri sar, metni geri alma.
Boş desen 0. Desen metinden uzunsa −1. Eşleşme baştaysa 0.
Naif her kayma O(nm). KMP metinde tek geçiş, desen failure’ı baştan kurulur.