📝 String Algorithms

Master pattern matching, string searching, and manipulation algorithms. Essential for text processing and bioinformatics.

Overview

ℹ️

What are String Algorithms?

String algorithms process and analyze text. They handle pattern matching (finding substrings), comparison (similarity, anagrams), transformation (editing, compressing), and analysis (palindromes, subsequences).

Key String Algorithms

KMP Pattern Matching

Linear-time pattern matching using prefix function

Time: O(n+m)Space: O(m)

Rabin-Karp

Pattern matching using rolling hash

Time: O(n+m) avg, O(nm) worstSpace: O(1)

Longest Common Subsequence

Find longest subsequence common to two strings

Time: O(n*m)Space: O(min(n,m))

Manacher's Algorithm

Find all palindromic substrings in O(n)

Time: O(n)Space: O(n)

Anagram Detection

Check if two strings are anagrams

Time: O(n)Space: O(1)

Interactive Visualizer

String Algorithm Visualization

📝

KMP Pattern Matching Visualizer

Watch string matching in action with character-by-character comparison highlighting.

Deep Dive: KMP Pattern Matching

Time Complexity

Time: O(n+m)

Space Complexity

Space: O(m)

Type

Pattern Matching

💡

Algorithm Approach

KMP computes an LPS array that stores the longest proper prefix which is also a suffix. When a mismatch occurs, we use LPS to skip characters we already know match, avoiding backtracking in the text.

python

def kmp(text, pattern):
    n, m = len(text), len(pattern)
    lps = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j-1]
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

1

Preprocess

Some algorithms (KMP, Manacher) need preprocessing of pattern/string.

2

Scan/Compare

Iterate through text/string, applying the core comparison logic.

3

Handle Mismatches

Use preprocessing info to skip redundant comparisons on mismatch.

4

Return Result

The answer is either match index, length, or boolean based on problem.

Real-World Applications

Text Editors

Find and replace, spell checking, auto-complete

Search Engines

Pattern matching in crawled documents, query suggestions

Bioinformatics

DNA sequence alignment and pattern matching

Network Security

Intrusion detection systems match attack patterns

Plagiarism Detection

String matching to find similar text passages

Compression

String algorithms for LZ77, LZW, and other compressors

Interview Questions

When would you use KMP over Rabin-Karp?

KMP has guaranteed O(n+m) time regardless of input. Rabin-Karp has O(n+m) average but O(nm) worst case. KMP is better when worst-case performance matters. Rabin-Karp is better for multi-pattern search (one hash, many patterns).

What is string hashing and its tradeoffs?

String hashing maps strings to integers for O(1) comparison. Rolling hash updates in O(1) as window slides. Tradeoff: hash collisions require verification. Use double hashing or large prime mod to reduce collisions.

How do you find longest palindromic substring efficiently?

Manacher's algorithm solves this in O(n). Expand around center approach is O(n²). DP is also O(n²) with O(n²) space. Manacher uses palindrome symmetry to avoid redundant expansions.

Knowledge Check

1. What is the time complexity of KMP?

2. What does LPS array store in KMP?

3. What technique does Rabin-Karp use?

4. Manacher's algorithm finds what in O(n)?

5. What is the space-optimized LCS approach?