Równoczesne zastępowanie kilku fraz w tekście

Łańcuchy znaków w językach programowania udostępniają zwykle operację zamiany wszystkich wystąpień jednego podciągu na inny. Nawet jeśli tak nie jest (co dotyczy chociażby C++, jak zwykle), możliwe jest jej łatwe zaimplementowanie przy pomocy prostszych funkcji (jak choćby std::string::find).
Gorzej jest z nieco bardziej skomplikowaną procedurą zastępowania kilku fraz naraz. Zaznaczam od razu, że nie jest to wcale równoważne wywołaniu funkcji typu Replace parę razy dla różnych argumentów. Jeśli bowiem zastąpimy w tekście X₁ przez Y₁, a w wyniku X₂ przez Y₂, to możemy otrzymać inny rezultat niż przy dokonywaniu obu zamian równocześnie – wystarczy, że Y₁ będzie w sobie zawierał ciąg X₂. W celu uzyskania poprawnego wyniku należy wszystkie zamiany przeprowadzać jednocześnie.

Prosta implementacja takiej operacji może się sprowadzać do przeglądania tekstu w poszukiwaniu któregoś z podciągów do zastąpienia, a następnie dokonania faktycznej zamiany dla tego z nich, który został wykryty najwcześniej w stosunku do aktualnej pozycji w tekście. Należy następnie przesunąć się tuż za znalezioną frazę i działanie powtórzyć – i tak aż do końca tekstu. W C++ wygląda to wszystko mniej więcej tak:

Jeśli tekst, na którym operujemy, ma długość n, a fraz do wyszukania i zastąpienia jest k, to w najgorszym przypadku całość może zabrać czas O(kn). Wymagałoby to jednak dość specyficznych danych, więc w praktyce nie musi być aż tak źle :) Dla lepszych rezultatów – zwłaszcza przy “obrabianiu” większej liczby tekstów tym samym słownikiem fraz – należałoby pewnie użyć specjalistycznych struktur danych, np. drzew prefiksowych (trie).