from collections import deque
from typing import List, Tuple, Optional
 
 
class AhoCorasickNode:
    """Klasa reprezentująca węzeł w drzewie Aho-Corasick."""
 
    def __init__(self):
        """Inicjalizuje węzeł drzewa."""
        self.goto = {}  # Przejścia do innych węzłów
        self.fail: Optional[AhoCorasickNode] = None  # Wskaźnik fail
        self.output: List[str] = []  # Lista wzorców kończących się w tym węźle
 
 
class AhoCorasick:
    """Klasa implementująca algorytm Aho-Corasick."""
 
    def __init__(self, patterns: List[str]):
        """
        Inicjalizuje automat Aho-Corasick dla podanych wzorców.
 
        Args:
            patterns: Lista wzorców do wyszukiwania
        """
        pass
 
    def _build_trie(self):
        """
        Buduje drzewo trie dla podanych wzorców.
        """
        pass
 
    def _build_failure_links(self):
        """Buduje wskaźniki fail dla automatu."""
        pass
 
    def search(self, text: str) -> List[Tuple[int, str]]:
        """
        Wyszukuje wszystkie wzorce w tekście.
 
        Args:
            text: Tekst do przeszukania
 
        Returns:
            Lista krotek (pozycja, wzorzec), gdzie pozycja to indeks początku wzorca w tekście
        """
        pass

patterns = ["he", "she", "his", "hers"]
text = "ushers"
Wynik: [(1, "she"), (2, "he"), (3, "hers")]