Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

String Matching in an Array

Problem (restated)

Return every word that is a substring of some other word in the array. Order is free.

Intuition

n ≤ 100, so pair every word as a pattern against every other as text. KMP (or contains) decides substring.

Approaches

KMP each pair

Unverified

Time O(n² · L)Space O(L)

Idea. For each words[i], KMP-search it in each words[j], j ≠ i. On a hit, keep it and skip the rest.

Walkthrough. ["mass","as","hero","superhero"] → as in mass, hero in superhero.

Trade-offs. Built-in contains is enough at this n. KMP is the pattern-aligned scan.

Solution

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;
}

Template connection

Repeated KMP exact match. Same search as LC 28.

Reflection

Each word is a pattern inside the others. Run KMP on every pair, and do not search a word inside itself.
A short word can sit inside a longer one. If the same word occurs twice, write it once as a pattern.
There is no empty word. A naive search returns the same words, at O(n * m) per pair.