String KMP¶

Table of Contents¶

28. Find the Index of the First Occurrence in a String¶

LeetCode | LeetCode CH (Easy)
Tags: two pointers, string, string matching

28. Find the Index of the First Occurrence in a String - Python Solution

from template import LPS


# Brute Force
def strStrBF(haystack: str, needle: str) -> int:
    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):
        if haystack[i : i + n] == needle:
            return i
    return -1


# KMP
def strStrKMP(haystack: str, needle: str) -> int:
    lps = LPS(needle)
    m, n = len(haystack), len(needle)
    j = 0

    for i in range(m):
        while j > 0 and haystack[i] != needle[j]:
            j = lps[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == n:
            return i - n + 1
    return -1


# |------------|------------------|---------|
# |  Approach  |       Time       |  Space  |
# |------------|------------------|---------|
# | Brute Force| O((m - n) * n)   | O(1)    |
# | KMP        | O(m + n)         | O(n)    |
# |------------|------------------|---------|


haystack = "hello"
needle = "ll"
print(strStrBF(haystack, needle))  # 2
print(strStrKMP(haystack, needle))  # 2

796. Rotate String¶

LeetCode | LeetCode CH (Easy)
Tags: string, string matching

796. Rotate String - Python Solution

# String
def rotateString(s: str, goal: str) -> bool:
    n = len(s)
    s += s

    for i in range(n):
        if s[i : i + n] == goal:
            return True

    return False


s = "abcde"
goal = "cdeab"
print(rotateString(s, goal))  # True

1392. Longest Happy Prefix¶

LeetCode | LeetCode CH (Hard)
Tags: string, rolling hash, string matching, hash function

1392. Longest Happy Prefix - Python Solution

from template import LPS


# KMP
def longestPrefix(s: str) -> str:
    if len(s) <= 1:
        return ""

    lps = LPS(s)

    return s[: lps[-1]]


print(longestPrefix("ababab"))  # abab

3036. Number of Subarrays That Match a Pattern II¶

LeetCode | LeetCode CH (Hard)
Tags: array, rolling hash, string matching, hash function

1764. Form Array by Concatenating Subarrays of Another Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, two pointers, greedy, string matching

1668. Maximum Repeating Substring¶

LeetCode | LeetCode CH (Easy)
Tags: string, dynamic programming, string matching

459. Repeated Substring Pattern¶

LeetCode | LeetCode CH (Easy)
Tags: string, string matching

459. Repeated Substring Pattern - Python Solution

from template import LPS


# KMP
def repeatedSubstringPattern(s: str) -> bool:
    lps = LPS(s)
    length = len(s)

    if lps[-1] != 0 and length % (length - lps[-1]) == 0:
        return True

    return False


s = "abab"
print(repeatedSubstringPattern(s))  # True

3008. Find Beautiful Indices in the Given Array II¶

LeetCode | LeetCode CH (Hard)
Tags: two pointers, string, binary search, rolling hash, string matching, hash function

214. Shortest Palindrome¶

LeetCode | LeetCode CH (Hard)
Tags: string, rolling hash, string matching, hash function

214. Shortest Palindrome - Python Solution

from template import LPS


# KMP
def shortestPalindrome(s: str) -> str:
    if not s:
        return s

    new = s + "#" + s[::-1]
    lps = LPS(new)

    add_len = len(s) - lps[-1]

    return s[::-1][:add_len] + s


print(shortestPalindrome("aacecaaa"))  # aaacecaaa

686. Repeated String Match¶

LeetCode | LeetCode CH (Medium)
Tags: string, string matching

686. Repeated String Match - Python Solution

import math

from template import LPS


# KMP
def repeatedStringMatch(a: str, b: str) -> int:
    min_repeat = math.ceil(len(b) / len(a))

    def kmp(text, pattern):
        n, m = len(text), len(pattern)
        lps = LPS(pattern)
        j = 0

        for i in range(n):
            while j > 0 and text[i] != pattern[j]:
                j = lps[j - 1]
            if text[i] == pattern[j]:
                j += 1
            if j == m:
                return i - j + 1
        return -1

    for i in range(min_repeat, min_repeat + 2):
        if kmp(a * i, b) != -1:
            return i
    return -1


print(repeatedStringMatch("abcd", "cdabcdab"))  # 3