1. String Algorithms:

Pattern Matching:

• Algorithms like the Knuth-Morris-Pratt (KMP) algorithm for efficient substring search.

def compute_lps_array(pattern):
    """
    Compute the Longest Prefix Suffix (LPS) array for the pattern.
    """
    lps = [0] * len(pattern)
    length = 0  # Length of the previous longest prefix suffix
    
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    return lps

def kmp_search(text, pattern):
    """
    Perform Knuth-Morris-Pratt (KMP) pattern matching algorithm.
    Returns a list of indices where the pattern is found in the text.
    """
    lps = compute_lps_array(pattern)
    i = 0  # Index for text
    j = 0  # Index for pattern
    indices = []

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            indices.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return indices

# Example usage:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
indices = kmp_search(text, pattern)

if indices:
    print(f"Pattern '{pattern}' found at indices:", indices)
else:
    print(f"Pattern '{pattern}' not found in the text.")

String Matching:

• Algorithms like the Rabin-Karp algorithm for searching for patterns within strings using hashing to efficiently compare substrings, making it suitable for large texts and patterns.

def rabin_karp_search(text, pattern):
    """
    Perform Rabin-Karp string matching algorithm.
    Returns a list of indices where the pattern is found in the text.
    """
    n = len(text)
    m = len(pattern)
    indices = []

    # Calculate hash values for pattern and first window of text
    pattern_hash = hash(pattern)
    text_hash = hash(text[:m])

    # Iterate through text to find matches
    for i in range(n - m + 1):
        if text_hash == pattern_hash and text[i:i + m] == pattern:
            indices.append(i)
        if i < n - m:
            # Update hash for next window in text
            text_hash = hash(text[i + 1:i + m + 1])

    return indices

# Example usage:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
indices = rabin_karp_search(text, pattern)

if indices:
    print(f"Pattern '{pattern}' found at indices:", indices)
else:
    print(f"Pattern '{pattern}' not found in the text.")

# output 
# Pattern 'ABABCABAB' found at indices: [10]