import numpy as np
def compute_transition_function(pattern):
    m = len(pattern)  
    TT = np.zeros((m+1, 26))
    pset = set() 
    for char in pattern:
        pset.add(char)
    
    for q in range(m + 1):
        for ch in pset:
            wa= pattern[:q] + ch
            k = min(m, q + 1)
            while (not (pattern[:k] == wa[-k:] ) and k>0):
                k -= 1
            
            TT[q][ord(ch)-ord('a')] = k   
    return TT

def finite_automaton_matcher(text, pattern):
    transition = compute_transition_function(pattern)
    q = 0  
    m = len(pattern)
    positions = []
    
    for i, char in enumerate(text):
        q = int(transition[q][ord(char)-ord('a')])  
        if q == m:
            positions.append(i - m + 1) 
    
    return positions

text = "theworldischangingtheexponentiallyandsoarewe" 
pattern = "the"
positions = finite_automaton_matcher(text, pattern)
print("Pattern found at positions:", positions)
