3
$\begingroup$

The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and withme), it takes a keyed set of N [before, after] pairs as an argument, and for each pair in the set, replaces all instances of <before> in the string with <after>.

For example, if we have this initial string:

three point one four one five

... and our set of [before, after] pairs looks like this:

[one, two]
[two, three]
[three, four]
[four, five]
[five, six]

... then after the operation completed, our updated string would be:

four point two five two six

The intuitive (but wrong) way to implement this would be to just iterate over the set and do a traditional search-and-replace for each pair in series. That works for cases where the values in the set are unrelated, but it fails in other cases (such as our example above) because the later iterations inappropriately operate on the results of the earlier operations. So doing it that way yields an incorrect result like this:

six point six six six six

My question is, there any well-known algorithm for handling this operation efficiently? I was able to come up with an algorithm that seems to accomplish it, but I suspect there might be a better way to do it than my hackish approach.

$\endgroup$
3
  • 3
    $\begingroup$ What in case one of the searched strings is a substring of another searched string ? $\endgroup$
    – user16034
    Mar 24, 2023 at 8:57
  • $\begingroup$ I would use regex. $\endgroup$ Mar 24, 2023 at 14:07
  • 1
    $\begingroup$ @YvesDaoust in that case one of them has to take priority -- in my implementation the pairs specified earlier in the set take priority over the ones specified later in the set, but I think it doesn't matter that much as long as the behavior is well-defined, documented, and deterministic. $\endgroup$ Mar 24, 2023 at 17:07

4 Answers 4

1
$\begingroup$

In principle: Starting with position I=0, check if one of your original strings is stored at position I. If not, increase i by 1. If yes, replace the string and set I = I + length of replacement. Note that an empty string as original string cannot be allowed.

To optimise: Make a table with the starting characters, look from position I until you find one of the starting characters, reducing the number of long comparisons.

$\endgroup$
3
$\begingroup$

You can build an Aho-Corasick automata for the before words, run your string through it, and whenever you find a match go back in the string and replace it with the after value, and then reset the automata. This takes linear time (in the length of both the input and output).

$\endgroup$
1
$\begingroup$

Well yeah, the Trie algorithm is a well-known technique for effectively performing this task. This technique can efficiently conduct numerous search-and-replace operations in a single pass over the input text, avoiding the problems that occur when the operations are performed in succession.

The temporal complexity of this approach is O(n + k), where n is the length of the input string and k is the total length of all 'before' strings. This is significantly quicker than doing the operations sequentially, which has a temporal complexity of O(n*k).

and also there are several Trie algorithm implementations available in many programming languages, thus it should be very simple to implement in your unique use case.

$\endgroup$
1
  • 1
    $\begingroup$ Is the Trie algorithm a different thing than the Trie data structure? (I get lots of hits for the latter but not so much for the former) $\endgroup$ Mar 24, 2023 at 21:51
-1
$\begingroup$

Store original: replacement in a map. Make an empty output string. Run through the string and word by word find new word using map and concatenate with output. return output.

$\endgroup$
1
  • $\begingroup$ Hmm, this approach seems to assume that the input string will be made out of (whitespace-separated) words and that the before/after pairs will consist of exactly one word apiece. I don't think that will be true in all cases. $\endgroup$ Mar 24, 2023 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.