Implementing Suffix-Based Algorithms

1. Implementing Suffix Array

Operation	Description	Time Complexity	Space Complexity
Build Suffix Array	Constructs an array of all suffixes sorted lexicographically	`O(n log n)`	`O(n)`
Search Suffix	Finds occurrences of a pattern in the text using binary search	`O(m log n)`	`O(1)`
LCP Array	Longest Common Prefix array for adjacent suffixes	`O(n)`	`O(n)`

Example: Building Suffix Array

function buildSuffixArray(text) {
  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));
  return suffixes.map(s => s.index);
}

const text = "banana";
console.log(buildSuffixArray(text)); // [5, 3, 1, 0, 4, 2]

Example: Searching with Suffix Array

function searchSuffixArray(text, pattern, suffixArray) {
  let left = 0;
  let right = suffixArray.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const suffix = text.slice(suffixArray[mid]);
    if (suffix.startsWith(pattern)) {
      return suffixArray[mid];
    } else if (suffix < pattern) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

const text = "banana";
const pattern = "ana";
const sa = buildSuffixArray(text);
console.log(searchSuffixArray(text, pattern, sa)); // 1

2. Building LCP Array

The Longest Common Prefix (LCP) array is used in conjunction with the suffix array to efficiently compute the longest common prefix between any two suffixes of a string. It is particularly useful in string matching and pattern searching algorithms.

Property	Description	Usage
lcp[i]	Length of the longest common prefix between suffixes starting at positions i and i+1 in the suffix array	Used to compute LCP values for adjacent suffixes

Example: Building LCP Array from Suffix Array

function buildLCPArray(s, suffixArray) {
  const n = s.length;
  const lcp = new Array(n).fill(0);
  const rank = new Array(n).fill(0);

  // Build rank array from suffix array
  for (let i = 0; i < n; i++) {
    rank[suffixArray[i]] = i;
  }

  let k = 0;
  for (let i = 0; i < n; i++) {
    if (rank[i] === 0) continue;
    let j = suffixArray[rank[i] - 1];
    while (i + k < n && j + k < n && s[i + k] === s[j + k]) {
      k++;
    }
    lcp[rank[i]] = k;
    if (k > 0) k--;
  }

  return lcp;
}

// Example usage:
const text = "banana";
const suffixArray = [5, 3, 1, 0, 4, 2]; // Suffix array of "banana"
const lcpArray = buildLCPArray(text, suffixArray);
console.log(lcpArray); // [0, 1, 3, 0, 0, 2]

Note: The LCP array construction algorithm uses the suffix array and rank array to compute the longest common prefix between adjacent suffixes in O(n) time.

3. Implementing Aho-Corasick Algorithm

The Aho-Corasick algorithm is a string searching algorithm that efficiently finds all occurrences of a set of patterns in a text. It uses a finite state machine built from a trie of the patterns.

Feature	Description	Notes
Time Complexity	O(n + m + z)	n = text length, m = total pattern lengths, z = number of matches
Space Complexity	O(m)	Where m is the total length of all patterns
Use Case	Multiple pattern matching	Efficient for large text and many patterns

Example: Aho-Corasick Implementation in JavaScript

class AhoCorasick {
  constructor(patterns) {
    this.root = {};
    this.fail = new Map();
    this.output = new Map();
    this.buildTrie(patterns);
    this.buildFailureFunction();
  }

  buildTrie(patterns) {
    for (let i = 0; i < patterns.length; i++) {
      let node = this.root;
      const pattern = patterns[i];
      for (let char of pattern) {
        if (!node[char]) node[char] = {};
        node = node[char];
      }
      node.output = true;
      this.output.set(i, pattern);
    }
  }

  buildFailureFunction() {
    const queue = [];
    for (let char in this.root) {
      const node = this.root[char];
      this.fail.set(node, this.root);
      queue.push(node);
    }

    while (queue.length > 0) {
      const current = queue.shift();
      for (let char in current) {
        const child = current[char];
        const failNode = this.fail.get(current);
        while (failNode !== this.root && !failNode[char]) {
          failNode = this.fail.get(failNode);
        }
        const newFail = failNode[char] || this.root;
        this.fail.set(child, newFail);
        queue.push(child);
      }
    }
  }

  search(text) {
    let node = this.root;
    const matches = [];
    for (let i = 0; i < text.length; i++) {
      const char = text[i];
      while (node !== this.root && !node[char]) {
        node = this.fail.get(node);
      }
      if (node[char]) {
        node = node[char];
      }

      if (node.output) {
        const patternIndex = Object.keys(node).find(key => key === 'output');
        matches.push({
          index: i - (this.output.get(patternIndex).length - 1),
          pattern: this.output.get(patternIndex)
        });
      }
    }
    return matches;
  }
}

const patterns = ['he', 'she', 'his', 'hers'];
const ac = new AhoCorasick(patterns);
console.log(ac.search('ushers'));

Note: The Aho-Corasick algorithm is particularly useful in applications like plagiarism detection, bioinformatics, and search engines where multiple keywords need to be matched simultaneously.

4. Building Failure Links

Component	Description	Usage
failureLink[i]	Points to the longest proper suffix of pattern[0..i] that is also a prefix of pattern	Used in KMP algorithm to avoid unnecessary comparisons
pattern	The input string for which failure links are computed	Input to the failure link construction algorithm

Example: Failure Link Construction

function buildFailureLinks(pattern) {
  const failureLink = 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 = failureLink[j - 1];
    }

    if (pattern[i] === pattern[j]) {
      j++;
    }

    failureLink[i] = j;
  }

  return failureLink;
}

// Example usage:
const pattern = "ABABCAB";
console.log(buildFailureLinks(pattern)); // [0, 0, 1, 2, 0, 1, 2, 3]

Note: The failure link array is crucial for the KMP (Knuth-Morris-Pratt) algorithm to achieve linear time complexity by avoiding redundant character comparisons.

5. Solving Multiple Pattern Search

Pattern	Description	Use Case	Time Complexity
Aho-Corasick	Efficient string matching for multiple patterns	Searching for multiple keywords in a text (e.g., malware detection)	O(n + m + z)
KMP (Knuth-Morris-Pratt)	Preprocessing to avoid redundant comparisons	Text search with a single pattern	O(n + m)
Z-Algorithm	Linear-time string matching using Z-array	Pattern matching in large texts	O(n)

Example: Aho-Corasick Implementation

class AhoCorasick {
  constructor(patterns) {
    this.root = {};
    this.fail = new Map();
    this.buildTrie(patterns);
    this.buildFailureLinks();
  }

  buildTrie(patterns) {
    for (const pattern of patterns) {
      let node = this.root;
      for (const char of pattern) {
        if (!node[char]) node[char] = {};
        node = node[char];
      }
      node.output = pattern;
    }
  }

  buildFailureLinks() {
    const queue = [];
    for (const key in this.root) {
      const node = this.root[key];
      queue.push(node);
      node.fail = this.root;
    }

    while (queue.length > 0) {
      const current = queue.shift();
      for (const key in current) {
        if (key === 'fail' || key === 'output') continue;
        const child = current[key];
        let failState = current.fail;

        while (failState !== this.root && !failState[key]) {
          failState = failState.fail;
        }

        if (failState[key]) {
          child.fail = failState[key];
        } else {
          child.fail = this.root;
        }

        queue.push(child);
      }
    }
  }

  search(text) {
    let node = this.root;
    const matches = [];

    for (let i = 0; i < text.length; i++) {
      const char = text[i];
      while (node !== this.root && !node[char]) {
        node = node.fail;
      }

      if (node[char]) {
        node = node[char];
      }

      if (node.output) {
        matches.push({
          pattern: node.output,
          index: i - node.output.length + 1
        });
      }
    }

    return matches;
  }
}

const patterns = ['he', 'she', 'his', 'hers'];
const ac = new AhoCorasick(patterns);
console.log(ac.search('His heart was hers')); // [{ pattern: 'his', index: 0 }, { pattern: 'he', index: 3 }, { pattern: 'hers', index: 12 }]

Note: The Aho-Corasick algorithm is particularly efficient for searching multiple patterns simultaneously in a large text.

6. Implementing Suffix Tree

Operation	Description	Time Complexity	Space Complexity
Build Suffix Tree	Constructs a tree from all suffixes of a string	O(n)	O(n)
Search Pattern	Finds all occurrences of a pattern in the string	O(m)	O(1)
Count Occurrences	Counts how many times a pattern appears	O(m)	O(1)
Longest Repeated Substring	Finds the longest substring that appears more than once	O(n)	O(1)

Example: Building a Suffix Tree

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

class SuffixTree {
  constructor(text) {
    this.text = text;
    this.root = new SuffixTreeNode();
    this.activeNode = this.root;
    this.activeEdge = -1;
    this.activeLength = 0;
    this.remainingSuffixCount = 0;
    this.leafEnd = -1;
    this.buildTree();
  }

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

  extendSuffixTree(pos) {
    this.leafEnd = pos;
    this.remainingSuffixCount++;
    while (this.remainingSuffixCount > 0) {
      if (this.activeLength === 0) {
        this.activeEdge = pos;
      }
      if (!this.root.children.has(this.text[this.activeEdge])) {
        this.root.children.set(this.text[this.activeEdge], new SuffixTreeNode());
        this.activeNode = this.root;
      } else {
        const child = this.root.children.get(this.text[this.activeEdge]);
        // Implementation continues...
      }
    }
  }
}

// Example usage:
const tree = new SuffixTree("banana");

Example: Searching in Suffix Tree

function searchPattern(node, pattern, index) {
  if (!node) return false;

  const patternLength = pattern.length;
  let i = 0;

  while (i < patternLength) {
    const edgeChar = node.text[node.start + i];
    if (edgeChar !== pattern[i]) {
      return false;
    }
    i++;
  }

  if (node.suffixIndex !== -1) {
    return true; // Found a complete match
  }

  // Continue searching in child nodes
  for (const child of node.children.values()) {
    if (searchPattern(child, pattern, index + 1)) {
      return true;
    }
  }

  return false;
}

// Example usage:
const found = searchPattern(tree.root, "ana", 0);
console.log(found); // true

Note: Suffix trees are powerful data structures for string matching problems, but they require significant space and are complex to implement.

7. Finding Longest Repeated Substring

Approach	Description	Time Complexity	Space Complexity
Suffix Array	Build a suffix array and find the longest common prefix (LCP) between adjacent suffixes	`O(n log n)`	`O(n)`
Suffix Tree	Build a suffix tree and find the deepest internal node with at least two leaf descendants	`O(n)`	`O(n)`
Binary Search + Rolling Hash	Use binary search on the length of repeated substring and rolling hash to check for matches	`O(n log n)`	`O(n)`

Example: Suffix Array Approach

function longestRepeatedSubstring(s) {
  const n = s.length;
  const suffixes = [];
  for (let i = 0; i < n; i++) {
    suffixes.push({ suffix: s.slice(i), index: i });
  }
  suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));

  let maxLength = 0;
  let resultIndex = 0;

  for (let i = 0; i < n - 1; i++) {
    let commonLength = 0;
    const minLen = Math.min(suffixes[i].suffix.length, suffixes[i + 1].suffix.length);
    for (let j = 0; j < minLen; j++) {
      if (suffixes[i].suffix[j] === suffixes[i + 1].suffix[j]) {
        commonLength++;
      } else {
        break;
      }
    }
    if (commonLength > maxLength) {
      maxLength = commonLength;
      resultIndex = suffixes[i].index;
    }
  }

  return s.slice(resultIndex, resultIndex + maxLength);
}

// Example usage:
console.log(longestRepeatedSubstring("banana")); // "ana"

Example: Rolling Hash Approach

function longestRepeatedSubstringRollingHash(s) {
  const n = s.length;
  const base = 256;
  const mod = 1000000007;

  function hasRepeatedSubstring(length) {
    if (length === 0) return true;
    let hash = 0;
    let power = 1;
    const hashes = new Map();

    for (let i = 0; i < length; i++) {
      hash = (hash * base + s.charCodeAt(i)) % mod;
      power = (power * base) % mod;
    }

    hashes.set(hash, 0);

    for (let i = 1; i <= n - length; i++) {
      hash = (hash * base - s.charCodeAt(i - 1) * power + s.charCodeAt(i + length - 1)) % mod;
      if (hashes.has(hash)) {
        const prevIndex = hashes.get(hash);
        if (s.slice(i, i + length) === s.slice(prevIndex, prevIndex + length)) {
          return true;
        }
      } else {
        hashes.set(hash, i);
      }
    }

    return false;
  }

  let left = 0;
  let right = n - 1;
  let resultLength = 0;
  let resultStart = 0;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (hasRepeatedSubstring(mid)) {
      resultLength = mid;
      resultStart = left;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return s.slice(resultStart, resultStart + resultLength);
}

// Example usage:
console.log(longestRepeatedSubstringRollingHash("banana")); // "ana"

8. Solving Palindrome Queries

Operation	Description	Time Complexity	Space Complexity
Check if string is palindrome	Verify if a string reads the same forwards and backwards	`O(n)`	`O(1)`
Find longest palindromic substring	Identify the longest contiguous substring that is a palindrome	`O(n^2)`	`O(1)`
Expand around centers	For each possible center, expand outward to find palindromes	`O(n^2)`	`O(1)`
Manacher's Algorithm	Optimized linear-time algorithm for longest palindromic substring	`O(n)`	`O(n)`

Example: Check if string is palindrome

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

Example: Find longest palindromic substring (Expand Around Centers)

function longestPalindrome(s) {
  if (s.length <= 1) return s;

  let start = 0;
  let maxLength = 1;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLength) {
        maxLength = right - left + 1;
        start = left;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // Odd-length palindromes
    expandAroundCenter(i, i + 1); // Even-length palindromes
  }

  return s.substring(start, start + maxLength);
}

console.log(longestPalindrome("babad")); // "bab" or "aba"
console.log(longestPalindrome("cbbd"));  // "bb"

Example: Manacher's Algorithm (Linear Time)

function manachers(s) {
  // Preprocess string to handle even-length palindromes
  let processed = '#' + s.split('').join('#') + '#';
  let P = new Array(processed.length).fill(0);
  let center = 0;
  let right = 0;

  for (let i = 0; i < processed.length; i++) {
    let mirror = 2 * center - i;

    if (i < right) {
      P[i] = Math.min(right - i, P[mirror]);
    }

    try {
      while (processed[i + P[i] + 1] === processed[i - P[i] - 1]) {
        P[i]++;
      }
    } catch (e) {}

    if (i + P[i] > right) {
      center = i;
      right = i + P[i];
    }
  }

  let maxLen = Math.max(...P);
  let centerIndex = P.indexOf(maxLen);
  let start = (centerIndex - maxLen) / 2;

  return s.substring(start, start + maxLen);
}

console.log(manachers("babad")); // "bab" or "aba"
console.log(manachers("cbbd"));  // "bb"

Note: Manacher's algorithm is optimal for finding the longest palindromic substring in linear time.

9. Implementing Z-Algorithm

The Z-algorithm is a linear-time string algorithm that computes the length of the longest substring starting at each position which matches a prefix of the string. It's particularly useful for pattern matching and string processing tasks.

Property	Description	Usage
Z-array	Array where Z[i] represents the length of the longest substring starting at index i that matches a prefix of the string.	Used to efficiently compute pattern occurrences in linear time.
Z-box	A range [l, r] where the substring from l to r matches a prefix of the string.	Used to optimize Z-array computation by avoiding redundant comparisons.

Example: Z-Algorithm Implementation

function zAlgorithm(str) {
  const n = str.length;
  const z = new Array(n).fill(0);
  let l = 0, r = 0;

  for (let i = 1; i < n; i++) {
    if (i <= r) {
      z[i] = Math.min(r - i + 1, z[i - l]);
    }

    while (i + z[i] < n && str[z[i]] === str[i + z[i]]) {
      z[i]++;
    }

    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }

  return z;
}

// Example usage:
const text = "ababab";
console.log(zAlgorithm(text)); // Output: [0, 0, 2, 0, 2, 0]

Note: The Z-algorithm runs in O(n) time and space, making it highly efficient for string pattern matching tasks.

10. Finding Distinct Substrings

Method	Description	Time Complexity	Space Complexity
Suffix Array	Builds an array of all suffixes sorted lexicographically	`O(n log n)`	`O(n)`
Suffix Tree	Tree structure storing all suffixes; allows efficient substring queries	`O(n)` for construction	`O(n)`
Rolling Hash	Uses hash functions to detect duplicate substrings efficiently	`O(n^2)` worst case, `O(n)` average	`O(n)`

Example: Suffix Array Implementation

function buildSuffixArray(str) {
  const suffixes = [];
  for (let i = 0; i <= str.length; i++) {
    suffixes.push({ suffix: str.slice(i), index: i });
  }
  suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
  return suffixes.map(s => s.index);
}

const text = "banana";
console.log(buildSuffixArray(text)); // [5, 3, 1, 0, 4, 2]

Example: Rolling Hash for Distinct Substrings

function countDistinctSubstrings(str) {
  const hashes = new Set();
  const base = 256;
  const mod = 1000000007;

  for (let i = 0; i < str.length; i++) {
    let hash = 0;
    for (let j = i; j < str.length; j++) {
      hash = (hash * base + str.charCodeAt(j)) % mod;
      hashes.add(hash);
    }
  }

  return hashes.size;
}

const text = "abc";
console.log(countDistinctSubstrings(text)); // 6

Note: The suffix array approach is preferred for large inputs due to its predictable performance and lower space usage compared to suffix trees.

11. Solving String Matching Variants

Variant	Description	Algorithm	Time Complexity
Exact String Matching	Find exact occurrence of a pattern in a text	KMP, Boyer-Moore, Rabin-Karp	O(n + m)
Wildcard Matching	Match pattern with wildcards like `*` or `?`	Dynamic Programming, NFA	O(nm)
Regular Expression Matching	Match patterns using regex syntax	NFA/DFA, Backtracking	O(nm)
Approximate String Matching	Find matches within a tolerance (Levenshtein distance)	Dynamic Programming, BK-Tree	O(nm)

Example: KMP Algorithm for Exact String Matching

function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

function KMPSearch(text, pattern) {
  const lps = buildLPS(pattern);
  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      console.log("Found pattern at index " + (i - j));
      j = lps[j - 1];
    } else if (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
}

Example: Wildcard Pattern Matching

function isMatch(s, p) {
  const dp = Array(s.length + 1)
    .fill()
    .map(() => Array(p.length + 1).fill(false));
  
  dp[0][0] = true;

  for (let j = 1; j <= p.length; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }

  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[s.length][p.length];
}

Note: The KMP algorithm uses a preprocessed "longest prefix suffix" array to avoid unnecessary character comparisons, making it efficient for exact string matching.