# KMP vs Z-Algorithm vs Rabin-Karp: Comparing String Matching Algorithms in JavaScript

> Explore KMP vs Z-Algorithm vs Rabin-Karp string matching in JavaScript. Discover their preprocessing, space needs, and performance for efficient substring search.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: comparison
- Published: 2026-02-24

---

**Knuth-Morris-Pratt (KMP), Z-Algorithm, and Rabin-Karp all solve the substring search problem in linear time, but differ in preprocessing methods, space requirements, and determinism—KMP uses a prefix table and guarantees O(n + m) performance with O(m) space, the Z-Algorithm leverages a Z-array on concatenated strings for the same complexity, while Rabin-Karp employs rolling hashes for O(1) extra space but requires collision verification.**

The `trekhleb/javascript-algorithms` repository provides a comprehensive collection of computer science implementations in JavaScript, including fundamental string matching techniques. While the repository currently ships with a production-ready KMP implementation in [`src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js), understanding how it compares to the Z-Algorithm and Rabin-Karp approaches helps developers choose the right tool for text searching tasks. Each algorithm offers distinct trade-offs between preprocessing overhead, memory usage, and worst-case guarantees.

## Knuth-Morris-Pratt (KMP) Algorithm

**KMP** guarantees deterministic linear time complexity by preprocessing the pattern to build a **prefix table** (also called the failure function). This table stores the length of the longest proper prefix which is also a suffix for each prefix of the pattern, allowing the algorithm to skip redundant comparisons when a mismatch occurs.

The implementation in `trekhleb/javascript-algorithms` runs in **O(n + m)** time with **O(m)** auxiliary space, where *n* is the text length and *m* is the pattern length. Because it never backtracks in the text, it performs well with streaming data and long patterns.

```javascript
// src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js
import knuthMorrisPratt from './knuthMorrisPratt.js';

const text = 'ababcabcabababd';
const pattern = 'ababd';
const index = knuthMorrisPratt(text, pattern); // → 10
console.log(`Pattern found at index ${index}`);

```

The prefix table construction requires a sequential scan of the pattern, making the implementation straightforward but slightly more complex than naive approaches. The repository provides a clean ES6 implementation with comprehensive test coverage.

## Z-Algorithm

The **Z-Algorithm** achieves the same **O(n + m)** worst-case time complexity as KMP but uses a different preprocessing strategy. It constructs a **Z-array** for the concatenated string `P$T` (pattern, separator, text), where each entry Z[i] represents the length of the longest substring starting at position *i* that matches a prefix of the concatenated string.

Space complexity is **O(n + m)** for the Z-array, though this is often effectively **O(m)** if built on-the-fly. While the Z-Algorithm is fully deterministic like KMP, it is currently **not implemented** in the `trekhleb/javascript-algorithms` master snapshot—the algorithm is documented but no source file exists.

```javascript
function zAlgorithmSearch(text, pattern) {
  const concat = pattern + '$' + text;
  const Z = new Array(concat.length).fill(0);
  let L = 0, R = 0;
  for (let i = 1; i < concat.length; i++) {
    if (i <= R) Z[i] = Math.min(R - i + 1, Z[i - L]);
    while (i + Z[i] < concat.length && concat[Z[i]] === concat[i + Z[i]]) Z[i]++;
    if (i + Z[i] - 1 > R) { L = i; R = i + Z[i] - 1; }
    if (Z[i] === pattern.length) return i - pattern.length - 1;
  }
  return -1;
}

```

This approach shines when you already need the Z-array for other string-processing tasks, such as longest-common-prefix queries, allowing you to solve multiple problems with a single preprocessing step.

## Rabin-Karp Algorithm

**Rabin-Karp** uses a **rolling hash** function to filter potential matches, computing a polynomial hash of the pattern and each *m*-length window of the text. This reduces the average time complexity to **O(n + m)** with only **O(1)** extra space, making it the most memory-efficient of the three approaches.

However, Rabin-Karp is probabilistic—hash collisions can cause false positives, requiring a character-by-character verification when hashes match. In the worst case (many collisions), performance degrades to **O(n × m)**. Like the Z-Algorithm, Rabin-Karp is **not present** in the current `trekhleb/javascript-algorithms` repository, though the concept is documented.

```javascript
function rabinKarpSearch(text, pattern) {
  const base = 256;
  const mod  = 101;               // a small prime
  const m = pattern.length, n = text.length;
  if (m === 0) return 0;
  let hashPat = 0, hashTxt = 0, h = 1;

  // The value of h = (base^(m-1)) % mod
  for (let i = 0; i < m - 1; i++) h = (h * base) % mod;

  // Initial hashes
  for (let i = 0; i < m; i++) {
    hashPat = (base * hashPat + pattern.charCodeAt(i)) % mod;
    hashTxt = (base * hashTxt + text.charCodeAt(i)) % mod;
  }

  // Slide the pattern over text
  for (let i = 0; i <= n - m; i++) {
    if (hashPat === hashTxt) {
      // Verify characters one-by-one to avoid false positives
      if (text.substr(i, m) === pattern) return i;
    }
    if (i < n - m) {
      hashTxt = (base * (hashTxt - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod;
      if (hashTxt < 0) hashTxt += mod;
    }
  }
  return -1;
}

```

Rabin-Karp excels in multiple-pattern search scenarios, where you can hash many patterns simultaneously and search a text for all of them in a single pass.

## Algorithm Comparison

Understanding the practical differences between these string matching algorithms helps determine which to implement for specific use cases:

- **Time Complexity**: KMP and Z-Algorithm guarantee **O(n + m)** in all cases. Rabin-Karp averages **O(n + m)** but can hit **O(n × m)** with poor hash distribution.

- **Space Requirements**: Rabin-Karp uses **O(1)** auxiliary space, KMP requires **O(m)** for the prefix table, and Z-Algorithm needs **O(n + m)** for the Z-array (though optimizable to **O(m)**).

- **Determinism**: KMP and Z-Algorithm are fully deterministic with no false positives. Rabin-Karp requires a verification step due to potential hash collisions.

- **Cache Performance**: Rabin-Karp offers excellent cache locality with minimal memory access. KMP performs well with its small prefix table, while the Z-Algorithm's larger array may impact cache performance on very long texts.

## When to Use Each Algorithm

Choose **KMP** when you need guaranteed linear performance with minimal memory overhead and want a well-tested implementation. According to the `trekhleb/javascript-algorithms` source code, this is the only algorithm of the three currently shipped with the repository, making it the safest default for production JavaScript applications.

Prefer the **Z-Algorithm** when you already require Z-array computation for other string analysis tasks, such as pattern prefix computations or longest-common-prefix queries. This allows you to amortize preprocessing costs across multiple operations.

Select **Rabin-Karp** when memory constraints are strict (embedded systems, large-scale text processing) or when searching for multiple patterns of the same length simultaneously. The rolling hash approach enables efficient multi-pattern matching that KMP and Z-Algorithm cannot easily achieve without significant modifications.

## Summary

- **KMP** provides deterministic **O(n + m)** performance using a prefix table, requires **O(m)** space, and is fully implemented in [`src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js).

- **Z-Algorithm** matches KMP's time complexity but uses a Z-array on concatenated strings, requiring more space but offering utility for other string problems; it is not currently implemented in the repository.

- **Rabin-Karp** offers average linear time with constant **O(1)** space using rolling hashes, but requires collision verification and is also absent from the current repository snapshot.

- KMP and Z-Algorithm are deterministic, while Rabin-Karp is probabilistic and best suited for multi-pattern searches or memory-constrained environments.

## Frequently Asked Questions

### Which string matching algorithm is fastest in JavaScript?

**KMP and Z-Algorithm both guarantee O(n + m) worst-case time**, making them theoretically equivalent and faster than naive O(n × m) approaches. In practice, Rabin-Karp may outperform them on average due to simple arithmetic operations and better cache locality, but its worst-case degradation to O(n × m) makes KMP the safer choice for deterministic performance. The V8 JavaScript engine optimizes array operations well, favoring KMP's prefix table lookups.

### Why would I choose Rabin-Karp over KMP?

**Choose Rabin-Karp when searching for multiple patterns simultaneously or when memory is severely constrained.** Because Rabin-Karp uses O(1) extra space and can compare pattern hashes in constant time, you can search for thousands of patterns efficiently by precomputing their hashes. KMP requires separate preprocessing for each pattern, making it less efficient for large pattern dictionaries despite its superior single-pattern performance.

### Is the Z-Algorithm better than KMP for single pattern matching?

**For single pattern matching, KMP and Z-Algorithm offer identical asymptotic performance**, but KMP is generally preferred due to lower space overhead. The Z-Algorithm requires constructing an array for the concatenated pattern-text string (size n + m), while KMP only stores a prefix table for the pattern (size m). However, if your application already computes Z-arrays for other purposes (like finding all occurrences or computing longest common prefixes), reusing that data structure makes the Z-Algorithm more efficient than running KMP separately.

### Does the trekhleb/javascript-algorithms repository include implementations for all three algorithms?

**No, the repository currently only includes Knuth-Morris-Pratt.** As of the master snapshot, implementations for Z-Algorithm and Rabin-Karp are absent, though the algorithms are documented in the repository's educational materials. The KMP implementation at [`src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js) is production-ready with full test coverage, while the other two would need to be implemented following the repository's ES6 coding standards if required.