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)

In C++, strings can be handled in two ways:

1. std::string (Recommended)
- Dynamic size, automatic memory management.
- Rich internal functions: .length(), .substr(), .find().
- Does NOT rely on a null terminator for logic (stores size explicitly).

2. C-Style Strings (char[])
- Fixed size arrays.
- Must be Null Terminated (\0).
- Manual memory management (easy to cause overflow).

Key Operations:
- Length: s.length() or s.size()
- Substring: s.substr(pos, len)
- Find: s.find("pattern") -> returns index or string::npos
- Concat: s1 + s2

C++ Code

#include <string>
using namespace std;

string s = "Hello";
int len = s.length();      // 5
string sub = s.substr(0,2); // "He"
int idx = s.find("ll");     // 2

Palindrome Check

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

Interactive

Loading visualizer...

A Palindrome reads the same forwards and backwards (e.g., "racecar", "madam").

Two Pointer Approach:
1. Initialize left = 0 and right = n - 1.
2. While left < right:
- If s[left] != s[right], return false.
- Increment left, Decrement right.
3. If loop finishes, return true.

C++ Code

bool isPalindrome(string s) {
    int l = 0, 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)

Interactive

Loading visualizer...

Knuth-Morris-Pratt (KMP) is an optimized pattern matching algorithm.

Problem with Naive Approach:
Naive matching checks every position, taking O(N * M) time. If you have a mismatch after matching 1000 characters, you shift by only 1 and re-check everything.

The KMP Solution:
KMP uses an LPS (Longest Prefix Suffix) array to skip unnecessary comparisons.
- LPS[i] tells us the length of the longest proper prefix that is also a suffix.
- If we mismatch at index j, we don't start over. We jump j to LPS[j-1].

Time Complexity: O(N + M) (Linear Time!)

C++ Code

// Compute LPS
vector<int> computeLPS(string& pat) {
    int m = pat.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    while(i < m) {
        if(pat[i] == pat[len]) {
             lps[i++] = ++len;
        } else {
             if(len != 0) len = lps[len-1];
             else lps[i++] = 0;
        }
    }
    return lps;
}

Rabin-Karp Algorithm

Avg: O(N+M) | Worst: O(N*M)

Rabin-Karp uses Hashing to find the pattern.

Concept:
1. Compute the Hash of the pattern.
2. Compute the Hash of the current window in text.
3. If Hashes match, compare actual characters (to avoid collisions).
4. Rolling Hash: Update the window hash in O(1) by subtracting the leaving char and adding the entering char.

Why use it?
Great for multiple pattern search (Plagiarism detection).

C++ Code

// Rolling Hash Formula
hash(s) = (s[0]*p^(n-1) + ... + s[n-1]*p^0) % MOD

// Update Hash
newHash = (oldHash - oldChar*bigPower) * p + newChar

Anagrams & Frequency Maps

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

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

Approaches:
1. Sorting: Sort both strings and compare. Time: O(N log N).
2. Frequency Array: Use an array of size 26 (for 'a'-'z') to count frequencies.
- Increment for string 1.
- Decrement for string 2.
- If all counts are 0, they are anagrams. Time: O(N).

C++ Code

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 i : count) if (i != 0) return false;
    return true;
}

Z-Algorithm

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

The Z-Algorithm constructs a Z-array where Z[i] is the length of the longest substring starting from s[i] which is also a prefix of s.

Application:
To search pattern P in text T:
1. Concatenate: S = P + "$" + T
2. Compute Z-array for S.
3. If Z[i] == P.length(), then pattern occurs at that position.

It is an alternative to KMP, often simpler to implement for certain problems.

C++ Code

// Z-Function Logic
for (int i = 1, l = 0, r = 0; 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;
}

// Compute LPS vector<int> computeLPS(string& pat) { int m = pat.size(); vector<int> lps(m, 0); int len = 0, i = 1; while(i < m) { if(pat[i] == pat[len]) { lps[i++] = ++len; } else { if(len != 0) len = lps[len-1]; else lps[i++] = 0; } } return lps; }

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 i : count) if (i != 0) return false; return true; }

// Z-Function Logic for (int i = 1, l = 0, r = 0; 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; }