#!/usr/bin/python3 # coding=utf8 # Zdrojový kód k úloze 29-Z1-5 Dva seznamy používající trie # Autorka: Katka Zákravská # Vstup programu: # Jsou zadané dva řádky -- dva seznamy jmen kamarádů. # Příklad seznamu: Franta Janka Zuzka Jenda Filip (jména jsou unikátní) # Výstup programu: # Jména kamarádů, kteří jsou v obou seznamech. # Poznámka: Uvažujeme pouze anglickou abecedu, malá písmenka. Je zde jedna # z mnoha možných implementací trie, kde v každém uzlu je pole o 26 políčkách # (indexujeme znaky abecedy). Existují samozřejmě i efektivnější implementace. ## Definice jednoho uzlu trie class Uzel: def __init__(self, s, ot): self.potomci = [None] * 26 # Jedno políčko pro každý znak abecedy self.konec = False # Označení, zda v uzlu končí nějaké slovo ## Funkce, která do trie přidá jedno slovo. def PridejDoTrie(trie, retezec): znak = retezec[0] # Přidávaný znak # Nestačí indexovat ascii hodnotou, je potřeba ji posunout, abychom se # dostali na rozmezí 0-25. Funkce ord(znak) vrací ascii hodnotu znaku. index = ord(znak) - ord('a') uzel = trie.potomci[index] if uzel == None: # Vrchol s daným symbolem ještě neexistuje. uzel = Uzel(znak, trie) # Vytvoření uzlu trie.potomci[index] = uzel if len(retezec) == 1: # Označíme konec slova. uzel.konec = True return # Jsme někde uprostřed slova, pokračujeme v přidávání vrcholů. Ubereme # první znak, který jsme právě přidali. return PridejDoTrie(uzel, retezec[1:len(retezec)]) ## Funkce, která v trii najde požadované slovo. def Najdi(trie, retezec): znak = retezec[0] index = ord(znak) - ord('a') uzel = trie.potomci[index] if uzel == None: # Pokud vrchol neexistuje, slovo v trii být nemůže. return False if len(retezec) == 1: # Jsme na posledním znaku slova if uzel.konec == True: # Vrchol je označený jako koncový, jupí! return True else: # Jméno jsme sice našli, ale tento kamarád nechtěl hrát první hru. # Viz Petr vs Petra return False else: # Jsme někde uprostřed slova, hledáme dál. return Najdi(uzel, retezec[1:len(retezec)]) ## Main # Načtení vstupu prvni_seznam = input().split() druhy_seznam = input().split() # Pokud už na vstupu dostaneme jeden ze seznamů prázdný, není co hledat. if len(prvni_seznam) == 0 or len(druhy_seznam) == 0: print("Žádný kamarád se nechce zúčastnit obou her.") sys.exit() trie = Uzel("", None) # Vytvoření prázdné trie, tj. jednoho vrcholu. # Postupně do trie přidáme všechna jména z prvního seznamu. for jmeno in prvni_seznam: PridejDoTrie(trie, jmeno) # Postupně zkusíme nalézt každé jméno z druhého seznamu v tom prvním, tedy # v trii. for jmeno in druhy_seznam: if Najdi(trie, jmeno): # Pokud jsme kamaráda našli, vypíšeme jeho jméno. print(jmeno)