String Algorithms and Pattern Matching Questions

def edit_distance(a: str, b: str) -> int:
    # Ensure we iterate over the smaller string for O(min(m,n)) space
    if len(a) < len(b):
        a, b = b, a  # make 'a' the longer string
    m, n = len(a), len(b)
    # prev and cur represent rows of length n+1
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        ai = a[i - 1]
        for j in range(1, n + 1):
            cost = 0 if ai == b[j - 1] else 1
            cur[j] = min(
                prev[j] + 1,        # deletion from a (or insert into b)
                cur[j - 1] + 1,     # insertion into a (or delete from b)
                prev[j - 1] + cost  # substitution / match
            )
        prev = cur
    return prev[n]

from typing import List

def compute_lps(p: str) -> List[int]:
    """Longest proper prefix which is also suffix for each prefix of p."""
    n = len(p)
    lps = [0] * n
    length = 0  # length of previous longest prefix-suffix
    i = 1
    while i < n:
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]  # fallback without advancing i
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text: str, pattern: str) -> List[int]:
    if not pattern:
        return list(range(len(text) + 1))  # convention: empty pattern matches at all positions
    lps = compute_lps(pattern)
    res = []
    i = j = 0  # i -> text, j -> pattern
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                res.append(i - j)
                j = lps[j - 1]  # continue searching for next match
        else:
            if j != 0:
                j = lps[j - 1]  # use lps to avoid re-checking matched prefix
            else:
                i += 1
    return res

def rabin_karp(text: str, pattern: str) -> list:
    """Return starting indices where pattern occurs in text."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []

    b = 257  # base (> alphabet size)
    M = 2**61 - 1  # large Mersenne prime, reduces overflow issues
    def modmul(a, b):  # safe modular multiplication for M=2^61-1
        prod = a * b
        # reduce using properties of Mersenne prime
        return (prod & M) + (prod >> 61) if (prod := a*b) < (1<<124) else ((prod & M) + (prod >> 61)) % M

    # precompute b^(m-1) mod M
    power = pow(b, m-1, M)

    # initial hash
    h_pat = 0
    h_win = 0
    for i in range(m):
        h_pat = (h_pat * b + ord(pattern[i])) % M
        h_win = (h_win * b + ord(text[i])) % M

    res = []
    for i in range(n - m + 1):
        if h_win == h_pat:
            # verify to avoid false positive due to hash collision
            if text[i:i+m] == pattern:
                res.append(i)
        if i + m < n:
            # remove leading char, add next char
            left = (ord(text[i]) * power) % M
            h_win = (h_win - left) % M
            h_win = (h_win * b + ord(text[i + m])) % M
    return res

# core checking routine and driver using double rolling hash + binary search
def longestDupSubstring(s):
    n = len(s)
    if n < 2:
        return ""

    base = 256
    mod1 = 2**61 - 1  # large Mersenne-like prime (use int64 safe)
    mod2 = 10**9 + 7

    def roll_hashes(L):
        """Return starting index of duplicate length-L substring or -1"""
        if L == 0:
            return -1
        h1 = 0
        h2 = 0
        power1 = pow(base, L, mod1)
        power2 = pow(base, L, mod2)
        seen = {}
        for i in range(L):
            h1 = (h1 * base + ord(s[i])) % mod1
            h2 = (h2 * base + ord(s[i])) % mod2
        seen[(h1, h2)] = [0]
        for start in range(1, n - L + 1):
            # remove leading char, add trailing char
            h1 = (h1 * base - ord(s[start - 1]) * power1 + ord(s[start + L - 1])) % mod1
            h2 = (h2 * base - ord(s[start - 1]) * power2 + ord(s[start + L - 1])) % mod2
            key = (h1, h2)
            if key in seen:
                # verify actual substring to avoid rare collision
                for prev in seen[key]:
                    if s[prev:prev+L] == s[start:start+L]:
                        return start
                seen[key].append(start)
            else:
                seen[key] = [start]
        return -1

    # binary search length
    lo, hi = 1, n - 1
    best_start, best_len = -1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        idx = roll_hashes(mid)
        if idx != -1:
            best_start, best_len = idx, mid
            lo = mid + 1
        else:
            hi = mid - 1

    return s[best_start:best_start + best_len] if best_start != -1 else ""