String matching algorithms

✅ 1. Naive Brute Force (Baseline)

🔍 Idea:

Try every possible position i in haystack where needle could start.
Check character-by-character if the substring starting at i matches needle.

⏱️ Time: O(n * m), where

• n = haystack.length()

• m = needle.length()

✅ Code:

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();

    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && haystack[i + j] == needle[j]) {
            j++;
        }
        if (j == m) return i; // Match found
    }

    return -1;
}

✅ 2. KMP (Knuth–Morris–Pratt)

🔍 Idea:

Use prefix-suffix pattern to avoid unnecessary comparisons.

• Build lps array (Longest Prefix which is also Suffix)

• While matching, when mismatch happens, use lps[] to jump

🧠 LPS Example for "aabaaac":

i:      0 1 2 3 4 5 6
str:    a a b a a a c
lps:    0 1 0 1 2 2 0

⏱️ Time: O(n + m)

✅ Code:

vector<int> buildLPS(string pattern) {
    int n = pattern.size();
    vector<int> lps(n, 0);
    int len = 0;

    for (int i = 1; i < n; ) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else {
            if (len == 0) i++;
            else len = lps[len - 1];
        }
    }

    return lps;
}

int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;

    vector<int> lps = buildLPS(needle);
    int i = 0, j = 0;

    while (i < haystack.size()) {
        if (haystack[i] == needle[j]) {
            i++; j++;
        }

        if (j == needle.size()) return i - j;

        else if (i < haystack.size() && haystack[i] != needle[j]) {
            if (j == 0) i++;
            else j = lps[j - 1];
        }
    }

    return -1;
}

✅ 3. Rabin-Karp (Rolling Hash)

🔍 Idea:

Use hashing to compare substring hashes instead of characters.

• Hash the needle

• Roll a hash window over the haystack

• On hash match, compare actual strings to avoid false positives

⏱️ Time:

• Average: O(n + m)

• Worst: O(n * m) (due to hash collisions)

✅ Code:

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m > n) return -1;

    const int base = 256;
    const int mod = 1e9 + 7;

    long long needleHash = 0, windowHash = 0, power = 1;

    for (int i = 0; i < m; i++) {
        needleHash = (needleHash * base + needle[i]) % mod;
        windowHash = (windowHash * base + haystack[i]) % mod;
        if (i != m - 1) power = (power * base) % mod;
    }

    for (int i = 0; i <= n - m; i++) {
        if (windowHash == needleHash) {
            if (haystack.substr(i, m) == needle) return i;
        }
        if (i < n - m) {
            windowHash = (windowHash - haystack[i] * power % mod + mod) % mod;
            windowHash = (windowHash * base + haystack[i + m]) % mod;
        }
    }

    return -1;
}

✅ 4. Z-Algorithm

🔍 Idea:

Z-array at position i tells us the length of the longest substring starting at i which is also a prefix.

Use it by combining:
needle + '$' + haystack

⏱️ Time: O(n + m)

✅ Code:

vector<int> computeZ(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;
}

int strStr(string haystack, string needle) {
    string combined = needle + "$" + haystack;
    vector<int> z = computeZ(combined);
    int m = needle.size();

    for (int i = 0; i < z.size(); i++) {
        if (z[i] == m) return i - m - 1;
    }

    return -1;
}

Summary Table

Algo Time Space Strength Naive O(n*m) O(1) Simple to write KMP O(n + m) O(m) Best general-purpose Rabin-Karp Avg O(n+m) O(1) Fast hash-based, good for multiple pattern matching Z-Algorithm O(n + m) O(n+m) Elegant for prefix matching