String Matching Patterns: Complete Reference¶

def kmp_search(text: str, pattern: str) -> list[int]:
    """
    Find all occurrences of pattern in text using KMP algorithm.

    Key insight: When mismatch occurs at position j in pattern,
    we don't restart from 0. Instead, we jump to failure[j-1]
    because that prefix has already been matched.

    Time: O(n + m) where n = len(text), m = len(pattern)
    Space: O(m) for the failure function
    """
    if not pattern:
        return [0]
    if not text or len(pattern) > len(text):
        return []

    # Build failure function
    pattern_length = len(pattern)
    failure = [0] * pattern_length

    # Compute failure function using self-matching
    prefix_length = 0
    for i in range(1, pattern_length):
        # Backtrack until we find a match or reach 0
        while prefix_length > 0 and pattern[i] != pattern[prefix_length]:
            prefix_length = failure[prefix_length - 1]

        if pattern[i] == pattern[prefix_length]:
            prefix_length += 1

        failure[i] = prefix_length

    # Search for pattern in text
    matches = []
    pattern_idx = 0

    for text_idx, text_char in enumerate(text):
        # Backtrack pattern pointer on mismatch
        while pattern_idx > 0 and text_char != pattern[pattern_idx]:
            pattern_idx = failure[pattern_idx - 1]

        if text_char == pattern[pattern_idx]:
            pattern_idx += 1

        if pattern_idx == pattern_length:
            # Found a match
            matches.append(text_idx - pattern_length + 1)
            # Continue searching (overlapping matches)
            pattern_idx = failure[pattern_idx - 1]

    return matches

def rabin_karp_search(text: str, pattern: str) -> list[int]:
    """
    Find all occurrences of pattern in text using Rabin-Karp.

    Key insight: Use rolling hash to compute hash of each window in O(1).
    hash(s[i:i+m]) can be computed from hash(s[i-1:i-1+m]) by:
    1. Remove contribution of s[i-1]
    2. Add contribution of s[i+m-1]

    Time: O(n + m) average, O(nm) worst case (hash collisions)
    Space: O(1) excluding output
    """
    if not pattern or len(pattern) > len(text):
        return []

    pattern_length = len(pattern)
    text_length = len(text)
    BASE = 256  # Character set size
    MOD = 10**9 + 7  # Large prime to reduce collisions

    # Compute hash of pattern and first window
    pattern_hash = 0
    window_hash = 0
    highest_power = 1  # BASE^(m-1) mod MOD

    for i in range(pattern_length):
        pattern_hash = (pattern_hash * BASE + ord(pattern[i])) % MOD
        window_hash = (window_hash * BASE + ord(text[i])) % MOD
        if i < pattern_length - 1:
            highest_power = (highest_power * BASE) % MOD

    matches = []

    # Slide the window
    for i in range(text_length - pattern_length + 1):
        if pattern_hash == window_hash:
            # Verify character by character (handle hash collision)
            if text[i:i + pattern_length] == pattern:
                matches.append(i)

        # Compute hash for next window
        if i < text_length - pattern_length:
            # Remove leading char, add trailing char
            window_hash = (window_hash - ord(text[i]) * highest_power) % MOD
            window_hash = (window_hash * BASE + ord(text[i + pattern_length])) % MOD
            window_hash = (window_hash + MOD) % MOD  # Handle negative

    return matches

class SolutionKMP:
    def strStr(self, haystack: str, needle: str) -> int:
        """
        Find first occurrence of needle in haystack using KMP.

        The KMP algorithm preprocesses the pattern to build a failure function.
        On mismatch, instead of restarting, we use the failure function to
        skip characters that we know will match.

        Time: O(m + n) where m = len(haystack), n = len(needle)
        Space: O(n) for the failure function
        """
        if not needle:
            return 0

        needle_length = len(needle)
        haystack_length = len(haystack)

        if needle_length > haystack_length:
            return -1

        # Build failure function (LPS array)
        # failure[i] = length of longest proper prefix of needle[0:i+1]
        # that is also a suffix
        failure: list[int] = [0] * needle_length

        prefix_length = 0
        for i in range(1, needle_length):
            # Backtrack until match or reach start
            while prefix_length > 0 and needle[i] != needle[prefix_length]:
                prefix_length = failure[prefix_length - 1]

            if needle[i] == needle[prefix_length]:
                prefix_length += 1

            failure[i] = prefix_length

        # Search using failure function
        needle_idx = 0

        for haystack_idx in range(haystack_length):
            haystack_char = haystack[haystack_idx]

            # On mismatch, use failure function to skip
            while needle_idx > 0 and haystack_char != needle[needle_idx]:
                needle_idx = failure[needle_idx - 1]

            if haystack_char == needle[needle_idx]:
                needle_idx += 1

            if needle_idx == needle_length:
                # Found first match
                return haystack_idx - needle_length + 1

        return -1

class SolutionRabinKarp:
    def strStr(self, haystack: str, needle: str) -> int:
        """
        Find first occurrence using Rabin-Karp rolling hash.

        Use polynomial rolling hash to compare windows in O(1) average.
        Verify on hash match to handle collisions.

        Time: O(m + n) average, O(mn) worst case
        Space: O(1)
        """
        if not needle:
            return 0

        needle_length = len(needle)
        haystack_length = len(haystack)

        if needle_length > haystack_length:
            return -1

        BASE = 256
        MOD = 10**9 + 7

        # Compute initial hashes
        needle_hash = 0
        window_hash = 0
        highest_power = 1

        for i in range(needle_length):
            needle_hash = (needle_hash * BASE + ord(needle[i])) % MOD
            window_hash = (window_hash * BASE + ord(haystack[i])) % MOD
            if i < needle_length - 1:
                highest_power = (highest_power * BASE) % MOD

        # Slide and compare
        for i in range(haystack_length - needle_length + 1):
            if needle_hash == window_hash:
                # Verify to avoid false positives
                if haystack[i:i + needle_length] == needle:
                    return i

            # Update hash for next window
            if i < haystack_length - needle_length:
                window_hash = (window_hash - ord(haystack[i]) * highest_power) % MOD
                window_hash = (window_hash * BASE + ord(haystack[i + needle_length])) % MOD
                window_hash = (window_hash + MOD) % MOD

        return -1

class SolutionKMP:
    def shortestPalindrome(self, s: str) -> str:
        """
        Find shortest palindrome by prepending characters to s.

        Key insight: Longest palindromic prefix of s equals the longest
        proper prefix of (s + '#' + reverse(s)) that is also a suffix.

        The '#' separator prevents false matches across the boundary.

        Time: O(n)
        Space: O(n)
        """
        if not s or len(s) <= 1:
            return s

        # Create concatenated string with separator
        reversed_s = s[::-1]
        concat = s + '#' + reversed_s

        # Build failure function
        concat_length = len(concat)
        failure: list[int] = [0] * concat_length

        prefix_length = 0
        for i in range(1, concat_length):
            while prefix_length > 0 and concat[i] != concat[prefix_length]:
                prefix_length = failure[prefix_length - 1]

            if concat[i] == concat[prefix_length]:
                prefix_length += 1

            failure[i] = prefix_length

        # failure[-1] = length of longest palindromic prefix
        palindrome_prefix_length = failure[-1]

        # Prepend reverse of non-palindromic suffix
        suffix_to_prepend = reversed_s[:len(s) - palindrome_prefix_length]

        return suffix_to_prepend + s

class SolutionRollingHash:
    def shortestPalindrome(self, s: str) -> str:
        """
        Use rolling hash to find longest palindromic prefix.

        Compute forward and backward hashes simultaneously.
        When they match at position i, s[0:i+1] is a palindrome.

        Time: O(n)
        Space: O(1)
        """
        if not s or len(s) <= 1:
            return s

        BASE = 29
        MOD = 10**9 + 7

        forward_hash = 0
        backward_hash = 0
        power = 1
        longest_palindrome_end = 0

        for i, char in enumerate(s):
            char_val = ord(char) - ord('a') + 1

            # Forward hash: h = h * BASE + char
            forward_hash = (forward_hash * BASE + char_val) % MOD

            # Backward hash: h = h + char * BASE^i
            backward_hash = (backward_hash + char_val * power) % MOD

            if forward_hash == backward_hash:
                # Potential palindromic prefix (may need verification)
                longest_palindrome_end = i

            power = (power * BASE) % MOD

        # Prepend reverse of suffix after longest palindromic prefix
        suffix = s[longest_palindrome_end + 1:]
        return suffix[::-1] + s

class SolutionKMP:
    def repeatedSubstringPattern(self, s: str) -> bool:
        """
        Check if string is built from repeated substrings using KMP.

        Property: For periodic string, failure[n-1] = n - period_length.
        So period_length = n - failure[n-1].
        String is periodic if period_length divides n and period_length < n.

        Time: O(n)
        Space: O(n)
        """
        string_length = len(s)

        if string_length <= 1:
            return False

        # Build failure function
        failure: list[int] = [0] * string_length

        prefix_length = 0
        for i in range(1, string_length):
            while prefix_length > 0 and s[i] != s[prefix_length]:
                prefix_length = failure[prefix_length - 1]

            if s[i] == s[prefix_length]:
                prefix_length += 1

            failure[i] = prefix_length

        # Check periodicity
        longest_prefix_suffix = failure[-1]

        if longest_prefix_suffix == 0:
            return False

        period_length = string_length - longest_prefix_suffix

        # Valid if period divides string length and is not the full string
        return string_length % period_length == 0

class SolutionConcatenation:
    def repeatedSubstringPattern(self, s: str) -> bool:
        """
        Elegant trick: s + s contains s at non-boundary position iff s is periodic.

        If s = "abab", then s + s = "abababab"
        Remove first and last char: "bababa"
        This still contains "abab" because it's periodic!

        Time: O(n) with efficient string search
        Space: O(n)
        """
        doubled = s + s
        # Remove first and last character to avoid trivial matches
        return s in doubled[1:-1]

class SolutionKMP:
    def longestPrefix(self, s: str) -> str:
        """
        Find longest happy prefix using KMP failure function.

        The failure function at position n-1 gives exactly what we need:
        the length of the longest proper prefix that is also a suffix.

        Time: O(n)
        Space: O(n)
        """
        string_length = len(s)

        if string_length <= 1:
            return ""

        # Build failure function
        failure: list[int] = [0] * string_length

        prefix_length = 0
        for i in range(1, string_length):
            while prefix_length > 0 and s[i] != s[prefix_length]:
                prefix_length = failure[prefix_length - 1]

            if s[i] == s[prefix_length]:
                prefix_length += 1

            failure[i] = prefix_length

        # The answer is directly failure[n-1]
        happy_prefix_length = failure[-1]

        return s[:happy_prefix_length]

class SolutionRollingHash:
    def longestPrefix(self, s: str) -> str:
        """
        Find longest happy prefix using rolling hash.

        Compute prefix and suffix hashes simultaneously.
        Track longest match where both hashes are equal.

        Time: O(n)
        Space: O(1)
        """
        string_length = len(s)

        if string_length <= 1:
            return ""

        BASE = 31
        MOD = 10**9 + 7

        prefix_hash = 0
        suffix_hash = 0
        power = 1
        longest_length = 0

        # Compare prefix s[0:i+1] with suffix s[n-i-1:n]
        for i in range(string_length - 1):
            prefix_char = ord(s[i]) - ord('a') + 1
            suffix_char = ord(s[string_length - 1 - i]) - ord('a') + 1

            # Prefix hash: h = h * BASE + char (left to right)
            prefix_hash = (prefix_hash * BASE + prefix_char) % MOD

            # Suffix hash: h = h + char * power (right to left, building from end)
            suffix_hash = (suffix_hash + suffix_char * power) % MOD

            power = (power * BASE) % MOD

            if prefix_hash == suffix_hash:
                longest_length = i + 1

        return s[:longest_length]

def build_failure(pattern: str) -> list[int]:
    """
    Build KMP failure function (LPS array).
    failure[i] = length of longest proper prefix of pattern[0:i+1]
                 that is also a suffix.
    Time: O(m), Space: O(m)
    """
    m = len(pattern)
    failure = [0] * m

    prefix_length = 0
    for i in range(1, m):
        while prefix_length > 0 and pattern[i] != pattern[prefix_length]:
            prefix_length = failure[prefix_length - 1]

        if pattern[i] == pattern[prefix_length]:
            prefix_length += 1

        failure[i] = prefix_length

    return failure

def kmp_search(text: str, pattern: str) -> int:
    """
    Find first occurrence of pattern in text.
    Time: O(n+m), Space: O(m)
    """
    if not pattern:
        return 0
    if len(pattern) > len(text):
        return -1

    failure = build_failure(pattern)
    pattern_idx = 0

    for text_idx, char in enumerate(text):
        while pattern_idx > 0 and char != pattern[pattern_idx]:
            pattern_idx = failure[pattern_idx - 1]

        if char == pattern[pattern_idx]:
            pattern_idx += 1

        if pattern_idx == len(pattern):
            return text_idx - len(pattern) + 1

    return -1

def rabin_karp(text: str, pattern: str) -> int:
    """
    Find first occurrence using rolling hash.
    Time: O(n+m) average, Space: O(1)
    """
    if not pattern:
        return 0
    m, n = len(pattern), len(text)
    if m > n:
        return -1

    BASE, MOD = 256, 10**9 + 7

    pattern_hash = window_hash = 0
    power = 1

    for i in range(m):
        pattern_hash = (pattern_hash * BASE + ord(pattern[i])) % MOD
        window_hash = (window_hash * BASE + ord(text[i])) % MOD
        if i < m - 1:
            power = (power * BASE) % MOD

    for i in range(n - m + 1):
        if pattern_hash == window_hash and text[i:i+m] == pattern:
            return i

        if i < n - m:
            window_hash = ((window_hash - ord(text[i]) * power) * BASE
                          + ord(text[i + m])) % MOD
            window_hash = (window_hash + MOD) % MOD

    return -1

def is_periodic(s: str) -> bool:
    """
    Check if string is built from repeated substrings.
    Time: O(n), Space: O(n)
    """
    n = len(s)
    if n <= 1:
        return False

    failure = build_failure(s)
    period = n - failure[-1]

    return failure[-1] > 0 and n % period == 0

def longest_happy_prefix(s: str) -> str:
    """
    Find longest proper prefix that is also suffix.
    Time: O(n), Space: O(n)
    """
    if len(s) <= 1:
        return ""

    failure = build_failure(s)
    return s[:failure[-1]]