Week 16: Advanced Strings — Z-Algorithm, Manacher's & Rabin-Karp

1. The Z-Algorithm

The Z-algorithm builds a Z-array for a string s, where z[i] is the length of the longest substring starting at i that matches a prefix of s (by convention, z[0] is left undefined or set to 0). To search for a pattern p in text t, build the Z-array of p + '#' + t (a separator character that appears in neither string) — every index in the t portion where z[i] equals p's length marks a match.

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

// O(n) time -- each index is visited a bounded number of times thanks to the [l, r] window
vector<int> buildZArray(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;   // [l, r] is the rightmost Z-box found so far

    for (int i = 1; i < n; i++) {
        if (i < r) {
            // i is inside a known matching window -- reuse a previously computed value
            z[i] = min(r - i, z[i - l]);
        }
        // extend the match past what the window already guaranteed
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > r) { l = i; r = i + z[i]; }   // grow the window if we extended past it
    }
    return z;
}

vector<int> findOccurrences(const string& pattern, const string& text) {
    string combined = pattern + "#" + text;
    vector<int> z = buildZArray(combined);
    vector<int> matches;

    int patternLen = pattern.size();
    for (int i = patternLen + 1; i < (int)combined.size(); i++) {
        if (z[i] == patternLen) {
            matches.push_back(i - patternLen - 1);   // convert back to an index into text
        }
    }
    return matches;
}

The [l, r] window is what makes this O(n) rather than the naive O(n²): whenever index i falls inside an already-known matching window, z[i - l] (the Z-value for the corresponding position near the start of the string) already tells you a safe lower bound for z[i] without rechecking characters one by one — the while loop then only needs to verify characters past what the window already guarantees. Every character gets compared inside that while loop at most a constant number of extra times across the whole run, which is the same amortized argument that keeps KMP's failure-function construction linear.

2. Manacher's Algorithm: Longest Palindromic Substring in O(n)

Week 4's expand-around-center approach checks every one of the 2n - 1 possible centers (each character, plus each gap between two characters, for even-length palindromes) and expands outward, costing O(n) per center and O(n²) overall. Manacher's algorithm reuses previously computed palindrome radii the same way the Z-algorithm reuses its window, bringing the total down to O(n).

The trick that avoids handling even- and odd-length palindromes as separate cases is to transform the string first, inserting a separator between every character (and at both ends) so every palindrome in the transformed string is odd-length: "aba" becomes "#a#b#a#", and "abba" becomes "#a#b#b#a#".

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

// O(n) time -- same amortized "reuse the window" argument as the Z-algorithm
string longestPalindrome(const string& s) {
    if (s.empty()) return "";

    // Transform: insert '#' between characters and at both ends
    string t = "#";
    for (char c : s) { t += c; t += '#'; }

    int n = t.size();
    vector<int> radius(n, 0);
    int center = 0, right = 0;   // rightmost palindrome boundary found so far

    for (int i = 0; i < n; i++) {
        if (i < right) {
            int mirror = 2 * center - i;               // i's mirror across `center`
            radius[i] = min(right - i, radius[mirror]);
        }
        // expand past what the mirror already guaranteed
        while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n &&
               t[i - radius[i] - 1] == t[i + radius[i] + 1]) {
            radius[i]++;
        }
        if (i + radius[i] > right) { center = i; right = i + radius[i]; }
    }

    int bestCenter = 0, bestRadius = 0;
    for (int i = 0; i < n; i++) {
        if (radius[i] > bestRadius) { bestRadius = radius[i]; bestCenter = i; }
    }
    // Map back to the original string: the palindrome spans [start, start + bestRadius)
    int start = (bestCenter - bestRadius) / 2;
    return s.substr(start, bestRadius);
}

radius[i] in the transformed string, divided by two, is exactly the length of the palindrome centered at that position in the original string — which is why inserting separators isn't just a convenience, it's what makes every center in the transformed string correspond cleanly to either a single character or a gap in the original.

3. Rabin-Karp: Multi-Pattern Search with Rolling Hash

Week 4 used a rolling hash to check a single pattern against a text. Rabin-Karp is the same rolling-hash idea applied to searching for many patterns at once: hash every pattern into a set first, then slide a same-length window across the text, updating its hash in O(1) per step, and check the set on every step instead of re-scanning every pattern individually.

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

const long long MOD = 1'000'000'007;
const long long BASE = 131;

long long hashOf(const string& s) {
    long long h = 0;
    for (char c : s) h = (h * BASE + c) % MOD;
    return h;
}

long long power(long long base, int exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Find every text index where any pattern of length `patternLen` starts a match.
// O(text.size() * patternLen) worst case for verification, O(text.size()) expected
// with a good hash and few collisions.
vector<int> searchAll(const vector<string>& patterns, const string& text, int patternLen) {
    unordered_map<long long, vector<string>> byHash;
    for (const string& p : patterns) byHash[hashOf(p)].push_back(p);

    vector<int> matches;
    if ((int)text.size() < patternLen) return matches;

    long long highPower = power(BASE, patternLen - 1, MOD);
    long long windowHash = hashOf(text.substr(0, patternLen));

    for (int i = 0; ; i++) {
        auto it = byHash.find(windowHash);
        if (it != byHash.end()) {
            // Hash collisions are possible -- verify with a real string comparison
            for (const string& p : it->second) {
                if (text.compare(i, patternLen, p) == 0) matches.push_back(i);
            }
        }
        if (i + patternLen >= (int)text.size()) break;

        // Roll the hash forward by one character in O(1)
        windowHash = (windowHash - text[i] * highPower % MOD + MOD) % MOD;
        windowHash = (windowHash * BASE + text[i + patternLen]) % MOD;
    }
    return matches;
}

Rolling the hash forward — subtracting the outgoing character's contribution and adding the incoming one — is what keeps each step O(1) instead of recomputing the whole window's hash from scratch. The verification step, text.compare(i, patternLen, p), is non-negotiable: a hash match is strong evidence of a real match but not proof, since two different strings can collide to the same hash, and skipping verification turns rare hash collisions into silent incorrect answers.

4. Comparing the Pattern-Matching Family

By now you have five tools that all answer some version of "find X in a string" — naive matching and KMP from Week 4, plus this week's Z-algorithm, Manacher's, and Rabin-Karp. Under interview time pressure, matching the tool to the exact question asked matters more than memorizing all five implementations equally well.

• Single pattern, single text: KMP or the Z-algorithm — both O(n + m), pick whichever you can implement correctly fastest.
• Many patterns, one text, same length: Rabin-Karp — hash every pattern once, then one O(n) sliding pass.
• Longest palindromic substring: Manacher's for the guaranteed O(n) answer; expand-around-center from Week 4 is a reasonable fallback if you can't recall Manacher's under pressure, since O(n²) still passes on modest input sizes.
• Many patterns, varying lengths: a trie (Week 11) is usually the better structural fit than repeated Rabin-Karp calls.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.