# 1. THE NAÏVE APPROACH
# Time: O(nm) worst case. Space: O(n + m), including lowercase copies.
def naive_search(text, pattern):
    text, pattern = text.lower(), pattern.lower()
    found = False

    for i in range(len(text) - len(pattern) + 1):
        match = True
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            print(f"Pattern found at index {i}")
            found = True

    if not found:
        print("Pattern not found in the text.")


text = input("Enter the main text: ")
pattern = input("Enter the pattern to search: ")
naive_search(text, pattern)


# 2. KMP (Knuth-Morris-Pratt Algorithm)
# LPS preprocessing: O(m) time and O(m) space.
def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            i += 1

    return lps


# Search: O(n + m) time and O(n + m) space, including lowercase copies.
def kmp_search(text, pattern):
    text, pattern = text.lower(), pattern.lower()
    if not pattern:
        for i in range(len(text) + 1):
            print(f"Pattern found at index {i}")
        return

    lps = compute_lps(pattern)
    i = j = 0
    found = False

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                print(f"Pattern found at index {i - j}")
                found = True
                j = lps[j - 1]
        elif j:
            j = lps[j - 1]
        else:
            i += 1

    if not found:
        print("Pattern not found in the text.")


text = input("Enter the main text: ")
pattern = input("Enter the pattern to search: ")
kmp_search(text, pattern)


# 3. RABIN-KARP
# Average time: O(n + m); worst-case time: O(nm). Space: O(n + m), including lowercase copies.
def rabin_karp_search(text, pattern):
    text, pattern = text.lower(), pattern.lower()
    n, m = len(text), len(pattern)
    if not pattern:
        for i in range(n + 1):
            print(f"Pattern found at index {i}")
        return

    base, prime = 256, 101
    pattern_hash = window_hash = 0
    highest_power = 1

    if m > n:
        print("Pattern not found in the text.")
        return

    for _ in range(m - 1):
        highest_power = highest_power * base % prime

    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        window_hash = (base * window_hash + ord(text[i])) % prime

    found = False
    for i in range(n - m + 1):
        if pattern_hash == window_hash and text[i:i + m] == pattern:
            print(f"Pattern found at index {i}")
            found = True
        if i < n - m:
            window_hash = (
                base * (window_hash - ord(text[i]) * highest_power)
                + ord(text[i + m])
            ) % prime

    if not found:
        print("Pattern not found in the text.")


text = input("Enter the main text: ")
pattern = input("Enter the pattern to search: ")
rabin_karp_search(text, pattern)


# 4. BOYER-MOORE
# Bad-character table: O(m) time and space.
def bad_char_heuristic(pattern):
    return {char: i for i, char in enumerate(pattern)}


# Search: O(nm) worst-case time; often sublinear on average. Space: O(n + m), including lowercase copies.
def boyer_moore_search(text, pattern):
    text, pattern = text.lower(), pattern.lower()
    n, m = len(text), len(pattern)
    if not pattern:
        for i in range(n + 1):
            print(f"Pattern found at index {i}")
        return

    bad_char = bad_char_heuristic(pattern)
    shift = 0
    found = False

    while shift <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[shift + j]:
            j -= 1

        if j < 0:
            print(f"Pattern found at index {shift}")
            found = True
            shift += m - bad_char.get(text[shift + m], -1) if shift + m < n else 1
        else:
            shift += max(1, j - bad_char.get(text[shift + j], -1))

    if not found:
        print("Pattern not found in the text.")


text = input("Enter the main text: ")
pattern = input("Enter the pattern to search: ")
boyer_moore_search(text, pattern)
