String Algorithms and Pattern Matching Questions

Approach: compute pattern hash and initial window hash using base=256 and mod=1_000_000_007. Slide window updating hash in O(1) by removing left char contribution and adding right char, multiplying/dividing by base via precomputed power. On hash match, verify by direct substring comparison to detect collisions.

import java.util.*;

public class RabinKarp {
    private static final long BASE = 256;
    private static final long MOD = 1_000_000_007L;

    // Returns list of start indices where pattern occurs in text
    public static List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (pattern == null || text == null) return result;
        int n = text.length(), m = pattern.length();
        if (m == 0 || m > n) return result;

        long patHash = 0, winHash = 0;
        long power = 1; // BASE^(m-1) % MOD

        for (int i = 0; i < m; i++) {
            patHash = (patHash * BASE + pattern.charAt(i)) % MOD;
            winHash = (winHash * BASE + text.charAt(i)) % MOD;
            if (i > 0) power = (power * BASE) % MOD;
        }

        for (int i = 0; i <= n - m; i++) {
            if (patHash == winHash) {
                // verify to handle collision
                if (text.regionMatches(i, pattern, 0, m)) result.add(i);
            }
            if (i < n - m) {
                // remove left char, multiply remaining by BASE, add next char
                long left = (text.charAt(i) * power) % MOD;
                winHash = (winHash - left + MOD) % MOD;        // remove left contribution
                winHash = (winHash * BASE) % MOD;             // shift window
                winHash = (winHash + text.charAt(i + m)) % MOD;// add new char
            }
        }
        return result;
    }

    // Example usage
    public static void main(String[] args) {
        System.out.println(search("abracadabra", "abra")); // [0,7]
    }
}

Key points:

• O(n) average time, O(1) extra space (excluding result). Each slide updates hash in O(1) using precomputed power = BASE^(m-1) % MOD.
• Collisions: detected by explicit substring comparison (regionMatches). This makes correctness deterministic.
• Edge cases: empty pattern, pattern longer than text, negative intermediate hash fixed by adding MOD.

Approach: Concatenate S = pattern + '$' + text and compute the Z-array in O(n). A Z value at index i gives the longest substring starting at i that matches prefix of S. Any Z at position i equal to len(pattern) that falls inside the text portion corresponds to a match; convert that i to a start index in text.

from typing import List

def z_search(text: str, pattern: str) -> List[int]:
    if not pattern:
        return list(range(len(text) + 1))  # empty pattern matches at every position
    S = pattern + '$' + text
    n = len(S)
    Z = [0] * n
    L = 0
    R = 0
    for i in range(1, n):
        if i <= R:
            Z[i] = min(R - i + 1, Z[i - L])
        while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] - 1 > R:
            L, R = i, i + Z[i] - 1

    res = []
    m = len(pattern)
    offset = m + 1  # start index of text within S
    for i in range(offset, n):
        if Z[i] >= m:
            res.append(i - offset)
    return res

Key points:

• Z computation runs in O(n) time with L/R window trick.
• Time: O(m + t) where m=len(pattern), t=len(text). Space: O(m + t).
  Edge cases:
• Empty pattern (matches at all positions).
• Pattern longer than text (returns []).
• Overlapping occurrences handled correctly.

Approach: Compute the LPS (longest proper prefix which is also suffix) table for the pattern, then scan the text using LPS to skip unnecessary comparisons. LPS lets us reuse previous match information so when a mismatch occurs we shift pattern by the largest proper prefix that is also a suffix, never re-checking characters in text that already matched.

public class KMP {
    // Build LPS array: lps[i] = length of longest proper prefix which is also suffix for pattern[0..i]
    public static int[] buildLPS(String pat) {
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0; // length of previous longest prefix suffix
        lps[0] = 0;
        int i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i++] = len;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // fallback without incrementing i
                } else {
                    lps[i++] = 0;
                }
            }
        }
        return lps;
    }

    // KMP search: returns list of start indices where pattern occurs in text
    public static java.util.List<Integer> search(String text, String pat) {
        java.util.List<Integer> res = new java.util.ArrayList<>();
        int n = text.length(), m = pat.length();
        if (m == 0) { // convention: empty pattern matches at every index
            for (int i = 0; i <= n; i++) res.add(i);
            return res;
        }
        int[] lps = buildLPS(pat);
        int i = 0, j = 0; // i -> text, j -> pattern
        while (i < n) {
            if (text.charAt(i) == pat.charAt(j)) {
                i++; j++;
                if (j == m) {
                    res.add(i - j);
                    j = lps[j - 1]; // continue searching for next possible match
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1]; // use LPS to avoid re-comparing text chars
                } else {
                    i++;
                }
            }
        }
        return res;
    }
}

Key points:

• lps lets us shift pattern to align the next possible match without moving text index back; matched text chars are never re-compared.
• Time: O(n + m), Space: O(m).
  Edge cases:
• Empty pattern, empty text, pattern longer than text, repeating patterns (e.g., "AAA"). Alternative: Z-algorithm or Rabin-Karp (probabilistic) but KMP gives deterministic linear worst-case.

The Z-algorithm computes for each position i in a string S the length Z[i] of the longest substring starting at i that matches the prefix of S. It runs in linear time by maintaining a window [L,R] (a Z-box) that matches a prefix and using previously computed Z-values to skip comparisons.

Manual Z-array for S = "aabcaabxaaz" (indices 0..10). Z[0] is conventionally 0.

Compare each suffix with the prefix:

• i=1: "abcaabxaaz" vs prefix "aab..." → match 'a' → Z[1]=1
• i=2: starts with 'b' ≠ 'a' → Z[2]=0
• i=3: 'c' ≠ 'a' → Z[3]=0
• i=4: "aabxaaz" matches prefix "aab" → Z[4]=3 (stops at 'x' vs 'c')
• i=5: within previous box; compare gives Z[5]=1
• i=6: 'b' ≠ 'a' → Z[6]=0
• i=7: 'x' ≠ 'a' → Z[7]=0
• i=8: "aaz" matches prefix "aa" → Z[8]=2
• i=9: "az" matches prefix 'a' → Z[9]=1
• i=10: 'z' ≠ 'a' → Z[10]=0

Final Z array: [0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 0]

Using Z-algorithm to search pattern P = "aabx" in text T:

1. Build S = P + '$' + T (use a separator character not in P or T).
2. Compute Z array for S.
3. For any position i in S, if Z[i] == |P|, then P occurs in T starting at index i - |P| - 1 (subtract the pattern and separator).

Example outline: if S = "aabx$...T..." and some Z[k] == 4, then pattern found at T-index k - 5. This gives all matches in O(|P|+|T|) time and O(|P|+|T|) space. Advantages: simple, linear-time, and avoids hashing; good when many matches or worst-case guarantees are needed.

Brief summary: The number of distinct substrings of s equals total substrings n(n+1)/2 minus sum of longest common prefixes between adjacent suffixes in a sorted order; equivalently you can compute it from a suffix automaton (SAM) as sum over states of (len[state] - len[link[state]]).

Method 1 — Suffix array + LCP

• Approach: build suffix array (SA) in O(n) or O(n log n) and LCP array (Kasai) in O(n). Number distinct = n*(n+1)/2 - sum(LCP[i]).
• Time: O(n) (using SA O(n) algorithms) or O(n log n) practically.
• Space: O(n) for SA, rank, LCP.
• Large alphabets: map characters to integers via coordinate compression (O(n log n) if sorting), or use radix if integers fit machine word; SA algorithms handle integer alphabets.
• Pros/cons: Simple to reason about; good when you also need sorted suffixes or suffix range queries. Memory is linear but constants include multiple arrays.

Method 2 — Suffix Automaton (SAM)

• Approach: build SAM online in O(n) time; each new character extends automaton; number distinct substrings = sum(len[v] - len[link[v]]) over all states.
• Time: O(n) (amortized), Space: O(n) states, edges sum O(n) for small alphabets but potentially O(n * alphabet) if naive.
• Large alphabets: implement transitions with hash maps (unordered_map) to avoid dense arrays; this increases per-op cost but keeps space proportional to number of transitions (O(n)).
• Pros/cons: Lower memory in practice (fewer arrays), incremental and stream-friendly, and fast for counting distinct substrings and substring-related DP queries. Slightly more coding complexity.

When to prefer which:

• Use SA when you need suffix ordering, LCP queries, or simpler implementation using libraries; SA has predictable array-based memory and can be fastest for small alphabets and memory-optimized implementations.
• Use SAM when you want streaming construction, minimal state count, or many substring queries (distinct counts, occurrences, longest common substring variants). For very large alphabets, implement SAM with hash maps to control memory; if memory is extremely tight and alphabet small, SA with compact integer arrays can be best.