Strings — Complete Step-by-Step Guide

Module 3 — String Manipulation & Pattern Matching Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. String Basics & Manipulation

A string is, at its core, an array of characters — which is why so many array techniques (traversal, two-pointer, reversal) apply directly to strings too. Common manipulations include reversing a string, checking whether it's a palindrome (reads the same forwards and backwards), counting character frequencies, and concatenation.

bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; 
        j--;
    }
    return true;
}
// isPalindrome("madam") -> true

2. Pattern Matching: Naive vs KMP

Pattern matching asks: does a smaller string (the "pattern") appear inside a larger string (the "text"), and if so, where?

• The Naive Approach: Checks every possible starting position in the text and compares character by character, giving $O(n \cdot m)$ time for a text of length $n$ and pattern of length $m$.
• KMP (Knuth-Morris-Pratt): Avoids re-checking characters they've already matched by precomputing how much of the pattern can be reused after a partial match (LPS — Longest Proper Prefix which is also a Suffix), bringing the time down to strictly linear $O(n + m)$.

// Naive pattern search
for (int i = 0; i <= n - m; i++) {
    int j = 0;
    while (j < m && text[i + j] == pattern[j]) j++;
    if (j == m) cout << "Found at index " << i << "\n";
}

• Complexity: Naive search — $O(n \cdot m)$. KMP — $O(n + m)$.