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

String Matching in an Array

Problem (yeniden ifade)

Dizideki başka bir kelimenin alt stringi olan her kelimeyi döndür. Sıra serbest.

Sezgi

n ≤ 100, her kelimeyi pattern, diğerlerini text yap. KMP (veya contains) karar verir.

Yaklaşımlar

Her çiftte KMP

Doğrulanmadı

Zaman O(n² · L)Alan O(L)

Fikir. Her words[i] için diğer words[j] içinde KMP ara. İsabet olunca tut, kalanı atla.

Yürüyüş. ["mass","as","hero","superhero"] → as mass içinde, hero superhero içinde.

Trade-off. Bu n’de built-in contains yeter. KMP kalıba uyar.

Çözüm

function isSubstr(text: string, pattern: string): boolean {
  if (pattern.length > text.length) return false;
  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;
  }
  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 true;
  }
  return false;
}

export function stringMatching(words: string[]): string[] {
  const res: string[] = [];
  for (let i = 0; i < words.length; i++) {
    for (let j = 0; j < words.length; j++) {
      if (i !== j && isSubstr(words[j]!, words[i]!)) {
        res.push(words[i]!);
        break;
      }
    }
  }
  return res;
}

function isSubstr(text: string, pattern: string): boolean {
  if (pattern.length > text.length) return false;
  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;
  }
  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 true;
  }
  return false;
}

export function stringMatching(words: string[]): string[] {
  const res: string[] = [];
  for (let i = 0; i < words.length; i++) {
    for (let j = 0; j < words.length; j++) {
      if (i !== j && isSubstr(words[j]!, words[i]!)) {
        res.push(words[i]!);
        break;
      }
    }
  }
  return res;
}

Şablon bağlantısı

Tekrarlı KMP tam eşleşme. LC 28 ile aynı arama.

Yansıma

Her kelime diğerlerinin içinde desen. KMP her çift. Kendini sayma.
Kısa kelime uzun olanın içinde. Aynı kelime iki kez duruyorsa desen olarak bir kez yazılır.
Boş kelime yok. Naif arama aynı cevabı verir, çift başına O(nm).