Pokonaj wyszukiwanie ciągów za pomocą algorytmu Aho-Corasick

Manipulowanie ciągami znaków i wyszukiwanie w nich wzorców to podstawowe zadania w data science i typowe zadanie dla każdego programisty.

Wydajne algorytmy łańcuchowe odgrywają ważną rolę w wielu procesach nauki o danych. Często to właśnie one sprawiają, że takie procesy są wystarczająco możliwe do praktycznego zastosowania.

W tym artykule poznasz jeden z najpotężniejszych algorytmów wyszukiwania wzorców w dużej ilości tekstu: algorytm Aho-Corasick. Algorytm ten wykorzystuje strukturę danych trie (wymawiane „try”) do śledzenia wzorców wyszukiwania i wykorzystuje prostą metodę do skutecznego znajdowania wszystkich wystąpień danego zestawu wzorców w dowolnym blobie tekstu.

Poprzedni artykuł na blogu Toptal Engineering przedstawiał algorytm wyszukiwania ciągów dla tego samego problemu. Podejście przyjęte w tym artykule zapewnia większą złożoność obliczeniową.

Algorytm Knutha-Morrisa-Pratta (KMP)

Aby zrozumieć, w jaki sposób możemy skutecznie szukać wielu wzorców w tekście, musimy najpierw rozwiązać łatwiejszy problem: szukanie pojedynczego wzorca w danym tekście.

Załóżmy, że mamy dużą plamę tekstu o długości N i wzorzec (którego chcemy poszukać w tekście) o długości M . Niezależnie od tego, czy chcemy szukać pojedynczego wystąpienia tego wzorca, czy wszystkich wystąpień, możemy osiągnąć złożoność obliczeniową O(N + M) za pomocą algorytmu KMP.

Funkcja prefiksu

Algorytm KMP działa poprzez obliczenie funkcji prefiksu szukanego wzorca. Funkcja prefiksu wstępnie oblicza pozycję rezerwową dla każdego prefiksu wzorca.

Zdefiniujmy nasz wzorzec wyszukiwania jako ciąg oznaczony jako S . Dla każdego podłańcucha S[0..i] , gdzie i >= 1 , znajdziemy maksymalny prefiks tego łańcucha, który również jest sufiksem tego łańcucha. Oznaczymy długość tego przedrostka P[i] .

W przypadku wzorca „abrakadabra” funkcja prefiksu wygeneruje następujące pozycje rezerwowe:

Funkcja prefiksu identyfikuje interesującą cechę wzorca.

Weźmy jako przykład konkretny przedrostek wzorca: „abrakadab”. Wartość funkcji prefiksu dla tego prefiksu to dwa. Wskazuje to, że dla tego przedrostka „aracadab” istnieje przyrostek o długości dwa, który dokładnie pasuje do przedrostka o długości dwa (tj. wzorzec zaczyna się od „ab”, a przedrostek kończy się na „ab.”) Ponadto jest to najdłuższe takie dopasowanie dla tego prefiksu.

Realizacja

Oto funkcja C#, której można użyć do obliczenia funkcji prefiksu dla dowolnego ciągu:

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

Uruchomienie tej funkcji na nieco dłuższym wzorcu „abcdabcabcdabcdab” daje to:

Złożoność obliczeniowa

Pomimo faktu, że istnieją dwie zagnieżdżone pętle, złożoność funkcji prefiksu jest po prostu O(M) , gdzie M jest długością wzorca S .

Można to łatwo wytłumaczyć obserwując, jak działają pętle.

Wszystkie iteracje pętli zewnętrznej przez i można podzielić na trzy przypadki:

1. Zwiększa k o jeden. Pętla kończy jedną iterację.

2. Nie zmienia zerowej wartości k . Pętla kończy jedną iterację.

3. Nie zmienia ani nie zmniejsza dodatniej wartości k .

Pierwsze dwa przypadki mogą działać najwyżej M razy.

W trzecim przypadku zdefiniujmy P(s, i) = k1 oraz P(s, i + 1) = k2, k2 <= k1 . Każdy z tych przypadków powinien być poprzedzony k1 - k2 wystąpieniami pierwszego przypadku. Liczba spadków nie przekracza k1 - k2 + 1 . A w sumie mamy nie więcej niż 2*M iteracje.

Wyjaśnienie drugiego przykładu

Spójrzmy na drugi przykładowy wzorzec „abcdabcabcdabcdab”. Oto jak funkcja prefiksu przetwarza go, krok po kroku:

1. Dla podciągu pustego i podciągu „a” o długości jeden, wartość funkcji prefiksu jest ustawiona na zero. ( k = 0 )

2. Spójrz na podciąg „ab”. Obecna wartość k wynosi zero, a znak „b” nie jest równy znakowi „a”. Tutaj mamy drugi przypadek z poprzedniej sekcji. Wartość k pozostaje na zero, a wartość funkcji prefiksu dla podłańcucha „ab” również wynosi zero.

3. To samo dotyczy podciągów „abc” i „abcd”. Nie ma przedrostków, które są jednocześnie przyrostkami tych podciągów. Wartość dla nich pozostaje na poziomie zero.

4. Przyjrzyjmy się teraz interesującemu przypadkowi, podłańcuchowi „abcda”. Bieżąca wartość k nadal wynosi zero, ale ostatni znak naszego podłańcucha pasuje do jego pierwszego znaku. To wyzwala warunek s[k] == s[i] , gdzie k == 0 oraz i == 4 . Tablica jest indeksowana przez zero, a k jest indeksem następnego znaku dla prefiksu o maksymalnej długości. Oznacza to, że znaleźliśmy prefiks o maksymalnej długości dla naszego podciągu, który jest również sufiksem. Mamy pierwszy przypadek, w którym nowa wartość k wynosi jeden, a zatem wartość funkcji prefiksu P(„abcda”) wynosi jeden.

5. Ten sam przypadek ma również miejsce dla następnych dwóch podciągów, P(“abcdab”) = 2 i P(“abcdabc”) = 3 . Tutaj szukamy naszego wzorca w tekście, porównując ciągi znak po znaku. Załóżmy, że pierwsze siedem znaków wzorca pasuje do siedmiu kolejnych znaków przetwarzanego tekstu, ale przy ósmym znaku nie pasuje. Co powinno się wydarzyć dalej? W przypadku naiwnego dopasowywania łańcuchów powinniśmy zwrócić siedem znaków wstecz i rozpocząć proces porównywania ponownie od pierwszego znaku naszego wzorca. Dzięki wartości funkcji prefiksu (tutaj P(„abcdabc”) = 3 ) wiemy, że nasz trzyznakowy sufiks pasuje już do trzech znaków tekstu. A jeśli następnym znakiem w tekście jest „d”, długość dopasowanego podciągu naszego wzorca i podłańcucha w tekście jest zwiększana do czterech („abcd”). W przeciwnym razie P(„abc”) = 0 i rozpoczniemy proces porównania od pierwszego znaku wzorca. Ale co ważne, nie wracamy w trakcie przetwarzania tekstu.

6. Następny podciąg to „abcdabca”. W poprzednim podciągu funkcja prefiksu była równa trzy. Oznacza to, że k = 3 jest większe od zera, a jednocześnie mamy niezgodność między kolejnym znakiem w prefiksie ( s[k] = s[3] = "d" ) a kolejnym znakiem w sufiksie ( s[i] = s[7] = "a" ). Oznacza to, że wywołaliśmy warunek s[k] != s[i] i że prefiks „abcd” nie może być sufiksem naszego łańcucha. Powinniśmy zmniejszyć wartość k i wziąć poprzedni prefiks do porównania, jeśli to możliwe. Jak opisaliśmy powyżej, tablica jest indeksowana od zera, a k jest indeksem następnego znaku, który sprawdzamy z prefiksu. Ostatni indeks aktualnie dopasowanego prefiksu to k - 1 . Bierzemy wartość funkcji prefiksu dla aktualnie dopasowanego prefiksu k = result[k - 1] . W naszym przypadku (trzeci przypadek) długość maksymalnego prefiksu zostanie zmniejszona do zera, a następnie w kolejnym wierszu zostanie zwiększona do jednego, ponieważ „a” to maksymalny prefiks będący jednocześnie sufiksem naszego podciągu.

7. (Tutaj kontynuujemy nasz proces obliczeniowy, aż dojdziemy do bardziej interesującego przypadku.)

8. Rozpoczynamy przetwarzanie następującego podłańcucha: „abcdabcabcdabcd”. Obecna wartość k to siedem. Podobnie jak w przypadku „abcdabca” powyżej, trafiliśmy na niedopasowanie: ponieważ znak „a” (siódmy znak) nie jest równy znakowi „d”, podłańcuch „abcdabca” nie może być sufiksem naszego ciągu. Teraz otrzymujemy już obliczoną wartość funkcji prefiksu dla „abcdabc” (trzy) i teraz mamy dopasowanie: Prefiks „abcd” jest również sufiksem naszego ciągu. Jego maksymalny prefiks i wartość funkcji prefiksu dla naszego podłańcucha to cztery, ponieważ taką właśnie stała bieżąca wartość k .

9. Kontynuujemy ten proces do końca wzoru.

W skrócie: oba cykle zajmują nie więcej niż 3 mi iteracje, co dowodzi, że złożoność wynosi O(M). Wykorzystanie pamięci jest również O(M).

Implementacja algorytmu KMP

 public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

Powyższy algorytm iteruje po tekście znak po znaku i próbuje zwiększyć maksymalny prefiks zarówno dla naszego wzorca, jak i pewnej sekwencji kolejnych znaków w tekście. W przypadku niepowodzenia nie wrócimy naszej pozycji do wcześniejszej pozycji w tekście. Znamy maksymalny prefiks znalezionego podciągu wzorca; ten prefiks jest również sufiksem znalezionego podciągu i możemy po prostu kontynuować wyszukiwanie.

Złożoność tej funkcji jest taka sama jak funkcji prefiksu, co sprawia, że ​​całkowita złożoność obliczeniowa O(N + M) z pamięcią O(M) .

Ciekawostka: Metody String.IndexOf() i String.Contains() w ramach platformy .NET mają pod maską algorytm o tej samej złożoności.

Algorytm Aho-Corasick

Teraz chcemy zrobić to samo dla wielu wzorów.

Załóżmy, że istnieje M wzorów o długościach L1 , L2 , …, Lm . Musimy znaleźć wszystkie dopasowania wzorców ze słownika w tekście o długości N .

Trywialnym rozwiązaniem byłoby wzięcie dowolnego algorytmu z pierwszej części i uruchomienie go M razy. Mamy złożoność O(N + L1 + N + L2 + … + N + Lm) , czyli O(M * N + L) .

Każdy wystarczająco poważny test zabija ten algorytm.

Wzięcie słownika zawierającego 1000 najpopularniejszych angielskich słów jako wzorców i użycie go do przeszukania angielskiej wersji „Wojny i pokoju” Tołstoja zajęłoby trochę czasu. Książka ma ponad trzy miliony znaków.

Jeśli weźmiemy 10 000 najpopularniejszych angielskich słów, algorytm będzie działał około 10 razy wolniej. Oczywiście na wejściach większych niż ten czas wykonania również wzrośnie.

To tutaj algorytm Aho-Corasick robi swoją magię.

Złożoność algorytmu Aho-Corasick to O(N + L + Z) , gdzie Z jest liczbą dopasowań. Algorytm ten został wynaleziony przez Alfreda V. Aho i Margaret J. Corasick w 1975 roku.

Realizacja

Tutaj potrzebujemy próby i dodajemy do naszego algorytmu podobny pomysł do funkcji prefiksowych opisanych powyżej. Obliczymy wartości funkcji prefiksu dla całego słownika.

Każdy wierzchołek w trie będzie przechowywać następujące informacje:

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

Istnieje wiele sposobów implementacji linków podrzędnych. Algorytm będzie miał złożoność O(N + L + Z) w przypadku tablicy, ale będzie to wymagało dodatkowej pamięci O(L * q) , gdzie q jest długością alfabetu, ponieważ jest to maksymalna liczba dzieci, które może mieć węzeł.

Jeśli użyjemy jakiejś struktury z dostępem O(log(q)) do jej elementów, to mamy dodatkowe wymaganie pamięciowe O(L) , ale złożoność całego algorytmu wyniesie O((N + L) * log(q) + Z) .

W przypadku tablicy mieszającej mamy dodatkową pamięć O(L) , a złożoność całego algorytmu wyniesie O(N + L + Z) .

Ten samouczek wykorzystuje tablicę mieszającą, ponieważ będzie ona również działać z różnymi zestawami znaków, np. chińskimi znakami.

Mamy już strukturę wierzchołka. Następnie zdefiniujemy listę wierzchołków i zainicjujemy węzeł główny tria.

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

Następnie dodajemy wszystkie wzory do próby. W tym celu potrzebujemy metody dodawania słów do triady:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

W tym momencie wszystkie słowa wzorca znajdują się w strukturze danych. Wymaga to dodatkowej pamięci O(L) .

Następnie musimy obliczyć wszystkie linki do sufiksów i linki do słowników.

Aby było to jasne i łatwe do zrozumienia, przejdę naszą próbę od korzenia do liści i dokonam podobnych obliczeń, jak dla algorytmu KMP, ale w przeciwieństwie do algorytmu KMP, w którym znajdujemy maksymalną długość prefiks, który również był sufiksem tego samego podciągu, teraz znajdziemy sufiks o maksymalnej długości bieżącego podciągu, który jest również prefiksem jakiegoś wzorca w tri. Wartością tej funkcji nie będzie długość znalezionego przyrostka; będzie to łącze do ostatniego znaku maksymalnego sufiksu bieżącego podciągu. To właśnie rozumiem przez przyrostek wierzchołka.

Przetwarzam wierzchołki według poziomów. W tym celu użyję algorytmu przeszukiwania wszerz (BFS):

A poniżej implementacja tego przejścia:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

A poniżej znajduje się metoda CalcSuffLink do obliczania linku sufiksu dla każdego wierzchołka (tj. wartość funkcji prefiksu dla każdego podłańcucha w tri):

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

Złożoność tej metody to O(L) ; w zależności od implementacji kolekcji podrzędnej złożoność może być O(L * log(q)) .

Dowód złożoności jest podobny do funkcji przedrostka dowodu złożoności w algorytmie KMP.

Spójrzmy na poniższy obraz. To jest wizualizacja próby słownika { abba, cab, baba, caab, ac, abac, bac } ze wszystkimi obliczonymi informacjami:

Krawędzie prób są ciemnoniebieskie, linki do sufiksów są jasnoniebieskie, a linki do sufiksów słownika są zielone. Węzły odpowiadające wpisom w słowniku są podświetlone na niebiesko.

A teraz potrzebujemy jeszcze tylko jednej metody — przetworzenia bloku tekstu, który zamierzamy przeszukać:

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

A teraz jest gotowy do użycia:

Na wejściu mamy listę wzorców:

 List<string> patterns;

I wyszukaj tekst:

 string text;

A oto jak to skleić:

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

I to wszystko! Wiesz już, jak działa ten prosty, ale potężny algorytm!

Aho-Corasick jest naprawdę elastyczny. Wzorce wyszukiwania nie muszą być tylko słowami, ale możemy używać całych zdań lub losowych łańcuchów znaków.

Występ

Algorytm został przetestowany na procesorze Intel Core i7-4702MQ.

Do testów wziąłem dwa słowniki: 1000 najpopularniejszych angielskich słów i 10 000 najpopularniejszych angielskich słów.

Aby dodać wszystkie te słowa do słownika i przygotować strukturę danych do pracy z każdym ze słowników, algorytm wymagał odpowiednio 55 ms i 135 ms.

Algorytm przetwarzał prawdziwe książki o długości 3-4 milionów znaków w ciągu 1,0-1,3 sekundy, podczas gdy w przypadku książki zawierającej około 30 milionów znaków zajęło to 9,6 sekundy.

Paralelizowanie algorytmu Aho-Corasick

Równolegle z algorytmem Aho-Corasick wcale nie jest problemem:

Duży tekst można podzielić na wiele porcji, a do przetworzenia każdej porcji można użyć wielu wątków. Każdy wątek ma dostęp do wygenerowanej próby na podstawie słownika.

A co ze słowami dzielonymi na granicy między kawałkami? Ten problem można łatwo rozwiązać.

Niech N będzie długością naszego dużego tekstu, S będzie rozmiarem kawałka, a L będzie długością największego wzorca w słowniku.

Teraz możemy zastosować prosty trik. Kawałki dzielimy z pewnymi nakładaniem się na końcu, na przykład biorąc [S * (i - 1), S * i + L - 1] , gdzie i jest indeksem kawałka. Kiedy otrzymamy dopasowanie do wzorca, możemy łatwo uzyskać indeks początkowy bieżącego dopasowania i po prostu sprawdzić, czy ten indeks znajduje się w zakresie porcji bez nakładania się, [S * (i - 1), S * i - 1] .

Wszechstronny algorytm wyszukiwania ciągów

Algorytm Aho-Corasick jest potężnym algorytmem dopasowywania ciągów znaków, który oferuje największą złożoność dla dowolnego wejścia i nie wymaga dużej ilości dodatkowej pamięci.

Algorytm jest często używany w różnych systemach, takich jak sprawdzanie pisowni, filtry spamu, wyszukiwarki, wyszukiwanie sekwencji bioinformatycznych/DNA itp. W rzeczywistości niektóre popularne narzędzia, z których możesz korzystać na co dzień, używają tego algorytmu za kulisami.

Funkcja prefiksu z algorytmu KMP sama w sobie jest ciekawym narzędziem, które sprowadza złożoność dopasowywania pojedynczego wzorca do czasu liniowego. Algorytm Aho-Corasick stosuje podobne podejście i wykorzystuje strukturę danych próbnych, aby zrobić to samo dla wielu wzorców.

Mam nadzieję, że ten samouczek dotyczący algorytmu Aho-Corasick okazał się przydatny.