from typing import Dict, Tuple, TypeVar, Any, Generic, Set

#######################################
# DO NOT CHANGE FOLLOWING DEFINITIONS #
ALPHABET = [chr(s) for s in range(ord("a"), ord("z") + 1)] + [" "]

Symbol = str
InT = TypeVar("InT")
OutT = TypeVar("OutT")


class GenericAutomaton(Generic[InT, OutT]):
    def __init__(
        self,
        init: InT,
        transition_table: Dict[Tuple[InT, Symbol], OutT],
        acc: Set[InT],
    ) -> None:

        self.alphabet = ALPHABET
        self.init = init
        self.transition_table = transition_table
        self.acc = acc


State = Any


class NFA(GenericAutomaton[State, Set[State]]):
    TransitionFunction = Dict[Tuple[State, Symbol], Set[State]]


class DFA(GenericAutomaton[State, State]):
    TransitionFunction = Dict[Tuple[State, Symbol], State]


def find(word: str, string: str) -> int:
    nfa = to_nfa(word)
    dfa = nfa_to_dfa(nfa)

    current = dfa.init
    for i in range(len(string)):
        current = dfa.transition_table[(current, string[i])]
        if current in dfa.acc:
            return i - (len(word) - 1)
    return -1


# DO NOT CHANGE PREVIOUS DEFINITIONS #
######################################


def to_nfa(word: str) -> NFA:
    pass  # TODO implement this


def nfa_to_dfa(nfa: NFA) -> DFA:
    pass  # TODO implement this


if __name__ == "__main__":
    assert find("hello", "hello world") == 0
    assert find("world", "hello world") == 6
    assert find("apple", "hello world") == -1
    # Add your own tests HERE