# 1. THE NAÏVE APPROACH
def naive_search(text, pattern):
    text_lower=text.lower()
    pattern_lower=pattern.lower()
    n = len(text_lower)
    m = len(pattern_lower)
    found = False
    
    # Loop through all possible starting positions in the text
    for i in range(n - m + 1):
        match = True
        
        # Check character by character for the current window
        for j in range(m):
            if text_lower[i + j] != pattern_lower[j]:
                match = False
                break  # Mismatch found, stop checking this window
        
        if match:
            print(f"Pattern found at index {i}")
            found = True
            
    if not found:
        print("Pattern not found in the text.")

# Get user input
print("--- Naive String Matching ---")
user_text = input("Enter the main text: ")
user_pattern = input("Enter the pattern to search: ")

naive_search(user_text, user_pattern)



# 2. KMP (Knuth-Morris-Pratt Algorithm)
def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0  # Length of the previous longest prefix suffix
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1] # Backtrack in pattern prefix
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    # Convert both strings to lowercase so matching ignores case differences
    text_lower = text.lower()
    pattern_lower = pattern.lower()
    
    n = len(text_lower)
    m = len(pattern_lower)
    lps = compute_lps(pattern_lower)
    print(f"Precomputed LPS Array: {lps}")
    
    i = 0  # Index for text
    j = 0  # Index for pattern
    found = False
    
    while i < n:
        if pattern_lower[j] == text_lower[i]:
            i += 1
            j += 1
        
        if j == m:
            print(f"Pattern found at index {i - j}")
            found = True
            j = lps[j - 1]  # Reset j using lps to find next match
            
        elif i < n and pattern_lower[j] != text_lower[i]:
            if j != 0:
                j = lps[j - 1]  # Don't reset i, just shift j backwards
            else:
                i += 1
                
    if not found:
        print("Pattern not found in the text.")

# Get user input
print("--- KMP String Matching ---")
user_text = input("Enter the main text: ")
user_pattern = input("Enter the pattern to search: ")

kmp_search(user_text, user_pattern)



# 3. RABIN-KARP 
def rabin_karp_search(text, pattern):
    # Convert both strings to lowercase so matching ignores case differences
    text_lower, pattern_lower = text.lower(), pattern.lower()
    n, m = len(text_lower), len(pattern_lower)
    found = False
    
    # Configuration for the hash function
    alphabet_size = 256  # Base multiplier (total characters in ASCII)
    prime = 101          # A prime number to reduce hash collision risk
    
    pattern_hash = 0
    window_hash = 0
    highest_power = 1  # Equivalent to (alphabet_size ** (m-1)) % prime

    # Calculate the multiplier factor for the oldest character in the window
    for i in range(m - 1):
        highest_power = (highest_power * alphabet_size) % prime

    # Edge case: pattern is longer than text
    if m > n:
        print("Pattern not found (Pattern is longer than text).")
        return

    #Calculate initial hash value for pattern and first text window
    for i in range(m):
        pattern_hash = (alphabet_size * pattern_hash + ord(pattern_lower[i])) % prime
        window_hash = (alphabet_size * window_hash + ord(text_lower[i])) % prime

    #Slide the pattern over text one by one
    for i in range(n - m + 1):
        # If hash values match, verify character by character to catch collisions
        if pattern_hash == window_hash:
            if text_lower[i : i + m] == pattern_lower:
                print(f"Pattern found at index {i}")
                found = True

        # Compute hash value for next window: Remove leading digit, add trailing digit
        if i < n - m:
            window_hash = (alphabet_size * (window_hash - ord(text_lower[i]) * highest_power) + ord(text_lower[i + m])) % prime
            
            # Convert negative hash values back to positive
            if window_hash < 0:
                window_hash = window_hash + prime

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

# Get user input
print("--- Rabin-Karp String Matching ---")
user_text = input("Enter the main text: ")
user_pattern = input("Enter the pattern to search: ")

rabin_karp_search(user_text, user_pattern)



# 4. BOYER-MOORE 
def bad_char_heuristic(pattern, size):
    # Initialize all characters in the alphabet table to -1
    # 256 represents the maximum possible ASCII characters
    bad_char = [-1] * 256

    # Fill the actual index position of each character present in the pattern
    for i in range(size):
        bad_char[ord(pattern[i])] = i
        
    return bad_char

def boyer_moore_search(text, pattern):
    # Convert both strings to lowercase so matching ignores case differences
    text_lower, pattern_lower = text.lower(), pattern.lower()
    n, m = len(text_lower), len(pattern_lower)
    
    # Precompute the Bad Character shift table
    bad_char = bad_char_heuristic(pattern_lower, m)
    
    # s represents the amount of shift of the pattern with respect to the text
    s = 0
    found = False
    
    while s <= (n - m):
        # Start checking characters from right to left (tail to head)
        j = m - 1
        
        # Keep reducing j while characters of pattern and text match
        while j >= 0 and pattern_lower[j] == text_lower[s + j]:
            j -= 1
            
        # If the pattern is present at the current shift, j will become -1
        if j < 0:
            print(f"Pattern found at index {s}")
            found = True
            
            # Shift the pattern so that the next character in text aligns with its last occurrence in pattern
            # If we reach the end of the text, shift by 1 position forward
            s += (m - bad_char[ord(text_lower[s + m])] if s + m < n else 1)
            
        else:
            # Mismatch occurred at character pattern[j]
            # Shift the pattern so that the bad character in text aligns with its last occurrence in pattern
            s += max(1, j - bad_char[ord(text_lower[s + j])])
            
    if not found:
        print("Pattern not found in the text.")

# Get user input
print("--- Boyer-Moore String Matching ---")
user_text = input("Enter the main text: ")
user_pattern = input("Enter the pattern to search: ")

boyer_moore_search(user_text, user_pattern)

