W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

String Algorithms

Master pattern matching, manipulation, and classic interview problems.

Topics

Minutes

O(N)

KMP Search

Visualizers

String Basics & Memory

Access: O(1) | Find: O(N * M) naive

Character Sequence Storage

Imagine a standard C++ std::string as an expanding accordion binder that handles its own memory resizing. In contrast, C-Style strings (char[]) are like a rigid row of mailboxes where the last mailbox must contain a special red flag (\0 null terminator) to indicate that the letter sequence is complete.

In C++, character sequences can be managed using two distinct layouts:

1. std::string (Class-Based)

Dynamic memory allocation under the hood.
Internal size tracker, meaning it doesn't need to scan for null terminators to get length (O(1) size lookup).
Safer against buffer overflow vulnerabilities.

2. C-Style Strings (Null-Terminated Arrays)

Fixed-size arrays of characters.
Must explicitly end with \0 so standard output and processing loops know where to stop scanning.

C++ Code — String Basics & Memory

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s = "Hello";
    int len = s.length();      // O(1) length check
    string sub = s.substr(0, 2); // Extract "He"
    
    size_t idx = s.find("ll"); // Returns index 2
    if (idx != string::npos) {
        cout << "Found pattern at: " << idx << endl;
    }
    return 0;
}

Palindrome Check

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

Interactive

Loading visualizer...

Symmetric String Layouts

Imagine folding a strip of paper in half. If the characters printed on both halves overlap and match perfectly, the word is a palindrome.

A string is a Palindrome if it reads the same forward and backward (e.g., "racecar", "madam").

Two-Pointer Algorithm:

Initialize pointers at the boundaries: left = 0 and right = n - 1.
While left < right:
- Compare characters at both pointers. If they do not match, return false immediately.
- Advance pointers: increment left++ and decrement right--.
If pointers meet or cross, the string is verified as a palindrome.

C++ Code — Palindrome Check

#include <string>
using namespace std;

bool isPalindrome(string s) {
    int l = 0;
    int r = s.length() - 1;
    
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

KMP Algorithm (Pattern Matching)

Time: O(N + M) | Space: O(M) for LPS array

Interactive

Loading visualizer...

Bookmarks for Skipping Re-checks

Imagine searching for a specific signature pattern in a long log book. When you hit a character mismatch, instead of flipping all the way back to the beginning of the signature, you check a bookmark index that tells you how much of the matched prefix can be reused to skip redundant checks.

The Knuth-Morris-Pratt (KMP) algorithm searches for occurrences of a pattern within a text in linear O(N + M) time.

The LPS (Longest Prefix Suffix) Array:

lps[i] stores the length of the longest proper prefix of the pattern substring pat[0..i] that is also a suffix of the same substring.
When a character mismatch occurs at index j in the pattern, we don't start comparing from the beginning of the pattern. Instead, we jump j back to lps[j - 1] and continue.

C++ Code — KMP Algorithm (Pattern Matching)

#include <vector>
#include <string>
using namespace std;

// Generate the LPS (Longest Prefix Suffix) lookup array
vector<int> computeLPS(string& pat) {
    int m = pat.size();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    
    while (i < m) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1]; // Use prefix history
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

Rabin-Karp Algorithm

Average: O(N + M) | Worst-case: O(N * M) due to collisions

Hash Fingerprinting

Imagine identifying a suspect. Instead of checking their detailed facial features character-by-character (which is slow), you check their unique fingerprint hash. Only when the hashes match do you perform a detailed visual inspection to avoid collision errors.

The Rabin-Karp algorithm uses hashing to search for a pattern in text:

Steps:

Compute the hash of the pattern.
Compute the hash of the current substring window in the text.
If the hashes match, compare actual characters to confirm.
Rolling Hash Optimization: Instead of recalculating the hash from scratch at each step (which takes O(M) time), we subtract the leaving character's value and add the entering character's value in O(1) time.

C++ Code — Rabin-Karp Algorithm

#include <string>
#include <vector>
using namespace std;

// Rabin-Karp Rolling Hash Formulation
// hash(s) = (s[0]*p^(m-1) + s[1]*p^(m-2) + ... + s[m-1]*p^0) % MOD
// To shift window: newHash = (oldHash - leavingChar * p^(m-1)) * p + enteringChar

Anagrams & Frequency Maps

Time: O(N) | Space: O(1) auxiliary

Inventory Sheet Matching

Imagine checking two grocery crates to see if they contain the exact same items. Instead of sorting all items, you count their frequencies. If crate A has 3 apples and 2 oranges, and crate B has 3 apples and 2 oranges, they match.

Two strings are Anagrams if they contain the same characters in the exact same frequencies (e.g., "listen" and "silent").

Optimal Check (Frequency Array):

Instead of sorting the strings (O(N log N) time), we can count frequencies using a fixed-size integer array of size 26 (representing 'a' through 'z'):

Increment the count for each character in string 1.
Decrement the count for each character in string 2.
If the final array contains only zeros, the strings are anagrams.

C++ Code — Anagrams & Frequency Maps

#include <string>
#include <vector>
using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    
    vector<int> count(26, 0);
    for (char c : s) count[c - 'a']++;
    for (char c : t) count[c - 'a']--;
    
    for (int val : count) {
        if (val != 0) return false;
    }
    return true;
}

Z-Algorithm

Time: O(N) | Space: O(N)

Linear Pattern Matching with Z-Arrays

The Z-Algorithm constructs a helper array Z where Z[i] represents the length of the longest substring starting at index i that matches the prefix of the string.

Pattern Matching Application:

To search for a pattern P in a text T:

Concatenate them with a special separator: S = P + "$" + T.
Compute the Z-array for S.
Any index i where Z[i] equals the length of P marks the start of a match.

C++ Code — Z-Algorithm

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    
    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

#include <iostream> #include <string> using namespace std; int main() { string s = "Hello"; int len = s.length(); // O(1) length check string sub = s.substr(0, 2); // Extract "He" size_t idx = s.find("ll"); // Returns index 2 if (idx != string::npos) { cout << "Found pattern at: " << idx << endl; } return 0; }

#include <string> using namespace std; bool isPalindrome(string s) { int l = 0; int r = s.length() - 1; while (l < r) { if (s[l] != s[r]) { return false; } l++; r--; } return true; }

#include <vector> #include <string> using namespace std; // Generate the LPS (Longest Prefix Suffix) lookup array vector<int> computeLPS(string& pat) { int m = pat.size(); vector<int> lps(m, 0); int len = 0; int i = 1; while (i < m) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; // Use prefix history } else { lps[i] = 0; i++; } } } return lps; }

#include <string> #include <vector> using namespace std; // Rabin-Karp Rolling Hash Formulation // hash(s) = (s[0]*p^(m-1) + s[1]*p^(m-2) + ... + s[m-1]*p^0) % MOD // To shift window: newHash = (oldHash - leavingChar * p^(m-1)) * p + enteringChar

#include <string> #include <vector> using namespace std; bool isAnagram(string s, string t) { if (s.length() != t.length()) return false; vector<int> count(26, 0); for (char c : s) count[c - 'a']++; for (char c : t) count[c - 'a']--; for (int val : count) { if (val != 0) return false; } return true; }

#include <vector> #include <string> #include <algorithm> using namespace std; vector<int> z_function(string s) { int n = s.length(); vector<int> z(n, 0); int l = 0, r = 0; for (int i = 1; i < n; i++) { if (i <= r) { z[i] = min(r - i + 1, z[i - l]); } while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { z[i]++; } if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z; }