Observatia cheie la aceasta problema era aceea ca putem calcula prin intermediul unei parcurgeri DFS valorile hash pentru lanturile
1 -> x
, respectiv x -> 1
(unde x
este nodul curent din parcurgere), daca acestea corespund, probabilitatea ca cele siruri sa difere este foarte mica, mai ales daca nu calculam o singura valoare hash, 2 sau chiar 3 valori hash diferite. Implementarea efectiva o lasam ca tema cititorilor.