String Algorithms

1. Naive String Matching

The simplest approach is to check every possible position in the text for a match with the pattern.

function naiveStringMatch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const positions = [];
  
  // Check each possible starting position in the text
  for (let i = 0; i <= n - m; i++) {
    let j;
    
    // Check if pattern matches at current position
    for (j = 0; j < m; j++) {
      if (text[i + j] !== pattern[j]) {
        break;
      }
    }
    
    // If we made it through the entire pattern, we found a match
    if (j === m) {
      positions.push(i);
    }
  }
  
  return positions;
}

// Example
const text = "ABABDABACDABABCABAB";
const pattern = "ABABC";
console.log(naiveStringMatch(text, pattern)); // [10]

2. Knuth-Morris-Pratt (KMP) Algorithm

KMP improves on the naive approach by avoiding redundant comparisons when a mismatch occurs. It uses a preprocessed array (called the "failure function" or "partial match table") to skip portions of the text.

The key insight is that when a mismatch occurs, we already know some information about the text from previous comparisons.

function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [];
  
  // Preprocessing: Build the LPS (Longest Prefix Suffix) array
  const lps = computeLPSArray(pattern);
  const n = text.length;
  const m = pattern.length;
  const positions = [];
  
  let i = 0; // Index for text
  let j = 0; // Index for pattern
  
  while (i < n) {
    // Current characters match
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }
    
    // Found a complete match
    if (j === m) {
      positions.push(i - j);
      j = lps[j - 1]; // Look for the next match
    }
    // Characters don't match
    else if (i < n && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1]; // Partial match, skip comparisons using LPS
      } else {
        i++; // No match at all, move to next character in text
      }
    }
  }
  
  return positions;
}

function computeLPSArray(pattern) {
  const m = pattern.length;
  const lps = Array(m).fill(0);
  
  let len = 0;
  let i = 1;
  
  while (i < m) {
    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;
}

String Reversal

// JavaScript string reversal
function reverseString(str) {
  return str.split('').reverse().join('');
}

// Manual implementation
function reverseStringManual(str) {
  let result = '';
  for (let i = str.length - 1; i >= 0; i--) {
    result += str[i];
  }
  return result;
}

Checking for Palindromes

function isPalindrome(str) {
  // Remove non-alphanumeric characters and convert to lowercase
  const cleanStr = str.replace(/[^A-Za-z0-9]/g, '').toLowerCase();
  
  // Two-pointer approach
  let left = 0;
  let right = cleanStr.length - 1;
  
  while (left < right) {
    if (cleanStr[left] !== cleanStr[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}