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

Repeated Substring Pattern

Problem (yeniden ifade)

s daha kısa bir stringin iki veya daha fazla kopyasının birleşimi mi?

Sezgi

s t’nin k ≥ 2 tekrarıysa LPS n - |t|’de biter. Periyot n - lps[n-1]; n’yi böler ve n’den küçükse döşer.

Yaklaşımlar

LPS periyot kontrolü

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. LPS kur. p = lps[n-1]. p > 0 && n % (n - p) == 0.

Yürüyüş. abab → son 2, periyot 2 → true. aba → son 1, periyot 2, 3%2 ≠ 0 → false.

Trade-off. s in (s+s)[1:-1] sevimli eşdeğer. LPS KMP açıklaması.

Çözüm

export function repeatedSubstringPattern(s: string): boolean {
  const n = s.length;
  if (n < 2) return false;
  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;
  }
  const p = lps[n - 1]!;
  return p > 0 && n % (n - p) === 0;
}

export function repeatedSubstringPattern(s: string): boolean {
  const n = s.length;
  if (n < 2) return false;
  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;
  }
  const p = lps[n - 1]!;
  return p > 0 && n % (n - p) === 0;
}

Şablon bağlantısı

LPS’den periyot; LC 28 / LC 1392 ile aynı dizi.

Yansıma

LPS’in sonu p. p > 0 ve n % (n-p) == 0 ise dizgi periyodik. Periyot n-p.
Tek karakter false. aba: lps 1, 3 ikiye bölünmez.
abcabc lps 3, periyot 3, true. Proper sonek tüm dizgi değildir.