Longest Happy Prefix

Problem (yeniden ifade)

Happy prefix, sonek de olan boş olmayan asıl önektir. En uzununu döndür; yoksa "".

Sezgi

Bu lps[n-1] tanımı. LPS kur, s[:lps[n-1]] al.

Yaklaşımlar

export function longestPrefix(s: string): string {
  const n = s.length;
  if (n === 0) return "";
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  return s.slice(0, lps[n - 1]!);
}

export function longestPrefix(s: string): string {
  const n = s.length;
  if (n === 0) return "";
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  return s.slice(0, lps[n - 1]!);
}

Şablon bağlantısı

Longest happy prefix = string’in LPS’si. LC 459 aynı son LPS değerini periyot olarak kullanır.

Yansıma

• Happy prefix, s’in LPS’sinin son değeri kadar önek. 0 ise boş dizgi.
• Proper: tüm dizgi sayılmaz. Tek karakter boş. aaaa üç a.
• Failure dizisi baştan kurulur. Önek ile sonek aynı harf dizisi olmalı, ortadan bir parça değil.