jsschools

Naive String Search

Checks every possible alignment of the pattern against the text using a two-pointer sliding comparison; simple but O(nm) in the worst case.

Spec ↗

Syntax

naiveSearch(text, pattern)

Parameters

NameTypeRequiredDescription
text string Yes The string to search within (length n).
pattern string Yes The pattern string to find (length m).

Returns

number[] — Array of starting indices where pattern occurs in text.

Examples

function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  const matches = [];
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) matches.push(i);
  }
  return matches;
}

console.log(naiveSearch('AABAACAADAABAABA', 'AABA'));
Output 
[ 0, 9, 12 ]

// Worst case: pattern like 'aaa' in 'aaaa...a' — many partial matches
function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length, res = [];
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) res.push(i);
  }
  return res;
}

const text = 'a'.repeat(10);
console.log(naiveSearch(text, 'aaa')); // overlapping matches
Output 
[ 0, 1, 2, 3, 4, 5, 6, 7 ]

Notes

| Case | Time | Space | |---------|-------|-------| | Best | O(n) | O(1) | | Average | O(nm) | O(1) | | Worst | O(nm) | O(1) | Worst case is O(nm): consider text = 'aaa...a' (n chars) and pattern = 'aaa...ab' (m-1 'a's + 'b') — each of the n-m+1 alignments scans m-1 characters before the mismatch. For alphabets with many distinct characters, the average case is much better than O(nm) because mismatches happen early. For performance-critical code use KMP, Z- algorithm, or the built-in `String.prototype.indexOf` (which may use Boyer-Moore-Horspool internally in JS engines).

See also