I have N strings and M search-replace pairs. Each of the strings contains exactly one of the search pair and the whole string needs to be replaced by the replace pair.Say you have returns,between,paragraphs and turn => foo, tween => bar, rag => baz then your output is foo, bar, baz.N can be a real big number while M is small. What's an efficient algorithm for this?
Replace strings based on substring match
algorithms;string matching
The most efficient algorithm would be to first construct a finite state machine that a) recognizes any of your keys, and b) has a different end state for each key, i. e. producing the index of the key that was recognized.Part a) is as easy as calling regcomp() appropriately. Unfortunately, this won't produce the index you need right away (part b)), it will just provide you with the beginning and end position of the recognized string.So, unless you want to go through the trouble of reimplementing a regex compilation routine, I guess your best bet is to subsequently look up the key from a hash table. However, again it is difficult to use a standard hash table implementation without triggering memory allocation by passing the key as a string. Of course, you can try to use a perfect hash for the lookup. Nevertheless, any compromise that takes you away from a finite state machine with the two properties a) and b) will incur a heavy slowdown.