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

Number of Subarrays That Match a Pattern II

Problem (yeniden ifade)

pattern[j] -1, 0 veya 1: sonraki değer düşsün, kalsın veya yükselsin. nums alt dizilerinden tüm pattern’i eşleyenleri say. n 1e6 olabilir, doğrusal zaman.

Sezgi

nums’u n-1 uzunlukta işaret akışına çevir. Pattern’in o akışta kaç kez geçtiğini say. KMP, eşleşmede durmadan j = lps[j-1] ve sayaç.

Yaklaşımlar

İşaret akışında KMP

Doğrulanmadı

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

Fikir. text[i] = sign(nums[i+1]-nums[i]). Pattern LPS. text’i tara; j == m olunca ans++, j = lps[j-1].

Yürüyüş. nums=[1,2,3,1,2,3], pattern=[1,1]. İki pencere. Örtüşen eşleşmeler serbest.

Trade-off. Naif pencereler 1e6’da TLE. LC 28 KMP, ilk indeks yerine sayım.

Çözüm

export function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const text: number[] = [];
  for (let i = 1; i < nums.length; i++) {
    const d = nums[i]! - nums[i - 1]!;
    text.push(d > 0 ? 1 : d < 0 ? -1 : 0);
  }
  const m = pattern.length;
  if (m === 0) return text.length + 1;
  const lps = new Array<number>(m).fill(0);
  let length = 0;
  for (let i = 1; i < m; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  let j = 0, ans = 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 === m) {
      ans++;
      j = lps[j - 1]!;
    }
  }
  return ans;
}

export function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const text: number[] = [];
  for (let i = 1; i < nums.length; i++) {
    const d = nums[i]! - nums[i - 1]!;
    text.push(d > 0 ? 1 : d < 0 ? -1 : 0);
  }
  const m = pattern.length;
  if (m === 0) return text.length + 1;
  const lps = new Array<number>(m).fill(0);
  let length = 0;
  for (let i = 1; i < m; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  let j = 0, ans = 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 === m) {
      ans++;
      j = lps[j - 1]!;
    }
  }
  return ans;
}

Şablon bağlantısı

Türetilmiş {-1,0,1} alfabesinde KMP. LC 28’in hepsini-say varyantı.

Yansıma

Metin, ardışık farkların işareti. Desenin işaretleri KMP ile bu metinde aranır. Eşit fark 0.
j desen boyuna varınca sayacı artır, j’yi lps[j-1] yap. Örtüşen eşleşmeler kaybolmasın.
Desen tek farksa metindeki o işaretler sayılır. Metin deseninden kısaysa 0.