#!/usr/bin/python3

# Doporučuji porovnat s implementací klasického KMP na
# https://ksp.mff.cuni.cz/viz/kucharky/hledani-v-textu/

jehla_pismena = "POTOPA"
seno_pismena = "ZAGHAHGZGHLQWUW"
J = len(jehla_pismena)
S = len(seno_pismena)
F = [None] * J  # Zpětná funkce

def na_cisla(slovo):
    posledni = [-1] * 26
    vysledek = [None] * len(slovo)
    for i, x in enumerate(slovo):
        ox = ord(x) - ord('A')
        if posledni[ox] == -1:
            vysledek[i] = 0
        else:
            vysledek[i] = i - posledni[ox]
        posledni[ox] = i
    return vysledek

def krok(i, znak):
    # Zde je právě upravené hledání kroku:
    if i < J and (jehla[i] == znak or (znak > i and jehla[i] == 0)):
        return(i + 1)
    elif i > 0:
        return krok(F[i - 1], znak)
    else:
        return 0

# Převod na čísla
jehla = na_cisla(jehla_pismena)
seno = na_cisla(seno_pismena)

# Konstrukce zpětné funkce
F[0] = 0
for i in range(1, J):
    F[i] = krok(F[i - 1], jehla[i])

# Procházení textu
stav = 0
for i in range(S):
    stav = krok(stav, seno[i])
    if stav == J:
        print(i - J + 1, "až", i)