Skip to main content
Mapagam

Comparing String Algorithm Patterns

1. Comparing String Matching Algorithms

Algorithm Time Complexity (Avg) Space Complexity Description
Naive String Matching O(n*m) O(1) Simple brute-force approach checking every position
KMP (Knuth-Morris-Pratt) O(n+m) O(m) Uses failure function to avoid redundant comparisons
Rabin-Karp O(n+m) average O(1) Uses hashing to find pattern, handles false positives
Boyer-Moore O(n*m) worst, O(n/m) best O(k) Bad character and good suffix heuristics for skipping
Aho-Corasick O(n + m + z) O(m) Efficient for multiple pattern matching in text

Example: KMP Algorithm Implementation

function buildFailureFunction(pattern) {
  const failure = new Array(pattern.length).fill(0);
  let j = 0;

  for (let i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = failure[j - 1];
    }
    if (pattern[i] === pattern[j]) {
      j++;
    }
    failure[i] = j;
  }

  return failure;
}

function kmpSearch(text, pattern) {
  const failure = buildFailureFunction(pattern);
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = failure[j - 1];
    }
    if (text[i] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      return i - pattern.length + 1;
    }
  }

  return -1;
}

Example: Rabin-Karp Implementation

function rabinKarp(text, pattern) {
  const d = 256; // Number of characters in alphabet
  const q = 101; // A prime number
  const n = text.length;
  const m = pattern.length;

  let p = 0; // Hash value for pattern
  let t = 0; // Hash value for text
  let h = 1;

  // Compute h = d^(m-1) % q
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % q;
  }

  // Calculate hash value of pattern and first window of text
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  // Slide the pattern over text one by one
  for (let i = 0; i <= n - m; i++) {
    // Check if hash values match
    if (p === t) {
      let j;
      for (j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) break;
      }
      if (j === m) return i; // Pattern found
    }

    // Calculate hash value for next window of text
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) t += q;
    }
  }

  return -1; // Not found
}

When to Use Which Algorithm

  • Naive: For small texts or when simplicity is preferred
  • KMP: When you need guaranteed linear time and want to avoid backtracking
  • Rabin-Karp: For multiple pattern searches or when hash collisions are acceptable
  • Boyer-Moore: For large alphabets and when pattern length is significant
  • Aho-Corasick: For searching multiple patterns simultaneously in large texts

2. Comparing String Hashing vs Trie

Feature String Hashing Trie
Time Complexity (Search) O(1) average, O(n) worst case O(m) where m is the length of the string
Space Complexity O(n) where n is the number of strings O(ALPHABET_SIZE × N × M) where N is number of strings and M is average length
Use Case Fast lookups when collisions are rare Prefix-based operations and memory-efficient storage of similar strings
Collision Handling Requires collision resolution (e.g., chaining or open addressing) No collisions; each character maps to a unique node
Prefix Matching Not efficient for prefix matching Highly efficient for prefix-based queries
Memory Usage Lower memory overhead for small datasets Higher memory usage due to node structure

Example: String Hashing

const hash = (str) => {
  let h = 0;
  for (let i = 0; i < str.length; i++) {
    h = (h * 31 + str.charCodeAt(i)) % 1000000007;
  }
  return h;
};

const strings = ["hello", "world", "algorithm"];
const hashTable = new Map();

strings.forEach(s => {
  const key = hash(s);
  if (!hashTable.has(key)) {
    hashTable.set(key, []);
  }
  hashTable.get(key).push(s);
});

console.log(hashTable); // Map with hashed keys and lists of strings

Example: Trie

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isEndOfWord = true;
  }

  search(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char);
    }
    return current.isEndOfWord;
  }

  startsWith(prefix) {
    let current = this.root;
    for (let char of prefix) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char);
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("hello");
trie.insert("world");
console.log(trie.search("hello")); // true
console.log(trie.startsWith("wor")); // true

Summary of Key Differences

  • Hashing is faster for exact matches but slower for prefix queries.
  • Trie excels in prefix-based searches and is more memory-efficient for strings with common prefixes.
  • Hashing may require handling collisions, while Trie avoids this entirely.

3. Comparing Suffix Array vs Suffix Tree

Feature Suffix Array Suffix Tree
Space Complexity O(n) O(n)
Time Complexity (Construction) O(n log n) O(n)
Time Complexity (Query) O(log n + k) for pattern search O(m) where m is pattern length
Memory Efficiency Highly memory efficient Higher memory overhead
Construction Algorithm Uses SA-IS or DC3 algorithm Builds tree structure from suffixes
Pattern Matching Requires binary search on array Direct traversal through tree
Use Case Memory-constrained environments Fast query performance required

Example: Suffix Array Construction

const text = "banana";
const suffixes = [];
for (let i = 0; i < text.length; i++) {
  suffixes.push({ index: i, suffix: text.slice(i) });
}
suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
const suffixArray = suffixes.map(s => s.index);
console.log(suffixArray); // [5, 3, 1, 0, 4, 2]

Example: Suffix Tree Construction

class SuffixTreeNode {
  constructor() {
    this.children = new Map();
    this.start = -1;
    this.end = -1;
  }
}

class SuffixTree {
  constructor(text) {
    this.root = new SuffixTreeNode();
    this.text = text;
    this.buildTree();
  }

  buildTree() {
    for (let i = 0; i < this.text.length; i++) {
      this.insertSuffix(i);
    }
  }

  insertSuffix(suffixStart) {
    let currentNode = this.root;
    for (let i = suffixStart; i < this.text.length; i++) {
      const char = this.text[i];
      if (!currentNode.children.has(char)) {
        const newNode = new SuffixTreeNode();
        currentNode.children.set(char, newNode);
      }
      currentNode = currentNode.children.get(char);
    }
  }
}

Key Differences Summary

  • Suffix Array is more space-efficient but slower for queries.
  • Suffix Tree offers faster query times but uses more memory.
  • Suffix arrays are easier to implement and understand for basic use cases.
  • Suffix trees provide better performance for complex string matching problems.

4. Comparing Rolling Hash vs Brute Force

Aspect Rolling Hash Brute Force
Time Complexity O(n) average case, O(nm) worst case O(nm)
Space Complexity O(1) O(1)
Use Case Searching for substring in large texts Small texts or when simplicity is preferred
Hash Function Uses polynomial rolling hash No hashing involved
Collision Handling Handles collisions with additional checks N/A

Example: Rolling Hash Implementation

function rollingHash(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const base = 256;
  const prime = 101;

  let hashPattern = 0;
  let hashText = 0;
  let h = 1;

  for (let i = 0; i < m - 1; i++) {
    h = (h * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    hashPattern = (hashPattern * base + pattern.charCodeAt(i)) % prime;
    hashText = (hashText * base + text.charCodeAt(i)) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (hashPattern === hashText) {
      let j;
      for (j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) break;
      }
      if (j === m) return i;
    }

    if (i < n - m) {
      hashText = (base * (hashText - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (hashText < 0) hashText += prime;
    }
  }

  return -1;
}

Example: Brute Force Implementation

function bruteForce(text, pattern) {
  const n = text.length;
  const m = pattern.length;

  for (let i = 0; i <= n - m; i++) {
    let j;
    for (j = 0; j < m; j++) {
      if (text[i + j] !== pattern[j]) break;
    }
    if (j === m) return i;
  }

  return -1;
}

Summary of Comparison

  • Rolling Hash is more efficient for large texts due to its average O(n) time complexity.
  • Brute Force is simpler to understand and implement, with consistent O(nm) complexity.
  • Rolling Hash requires handling hash collisions, which can increase complexity.
  • Brute Force does not require any hash computations or collision handling.

5. Selecting String Algorithm Strategy

String Algorithm Strategy Selection

  • Exact Matching: Use KMP or Boyer-Moore for high-performance substring search in large texts.
  • Pattern with Wildcards: Regular Expressions or Aho-Corasick for complex pattern matching with wildcards.
  • Approximate Matching: Use Levenshtein Distance or Soundex for fuzzy string matching.
  • Multiple Pattern Search: Aho-Corasick or Finite Automata for searching multiple patterns simultaneously.
  • Memory-Constrained Environments: Rabin-Karp for its simplicity and low memory usage.
Algorithm Time Complexity (Avg) Space Complexity Best Use Case
KMP (Knuth-Morris-Pratt) O(n + m) O(m) Exact matching with no wildcards
Boyer-Moore O(n * m) worst, O(n/m) best O(k) Large texts with short patterns
Rabin-Karp O(n + m) average O(1) Simple implementation, low memory
Aho-Corasick O(n + z + m) O(m) Multiple pattern matching
Regular Expressions O(n * m) Varies Complex pattern matching with wildcards

Example: Using KMP for Exact Matching

function buildFailureTable(pattern) {
  const table = new Array(pattern.length).fill(0);
  let j = 0;
  for (let i = 1; i < pattern.length; i++) {
    if (pattern[i] === pattern[j]) {
      table[i] = ++j;
    } else if (j > 0) {
      j = table[j - 1];
      i--; // Recheck current index
    }
  }
  return table;
}

function kmpSearch(text, pattern) {
  const failureTable = buildFailureTable(pattern);
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = failureTable[j - 1];
    }
    if (text[i] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      return i - pattern.length + 1;
    }
  }
  return -1;
}

const text = "ABABDABACDABABCABCABCABCABC";
const pattern = "ABABCABCABCABC";
console.log(kmpSearch(text, pattern)); // Output: 10

Was this article helpful?

Related Cheat Sheets