Programing Challenge: Replace String Pairs

By Xah Lee. Date: 2013-02-23

A coding challenge.

write a function “replace_string_pairs”. The function will take a ‹input string› and ‹pairs›, and returns a string.

the ‹pairs› is a list of pairs:

[
 [‹search string 1›, ‹replace string 1›]
 [‹search string 2›, ‹replace string 2›]
 [‹search string 3›, ‹replace string 3›]
 …
]

but here's the tricky part:

Once a subsring in the input string is replaced, that part is not changed again. (the replacement start with first pair, then second, etc) For example:

# -*- coding: utf-8 -*-
# python 3

replace_string_pairs("abcd", [["a", "c"], ["c", "d"]])

then, result should be "cbdd", not "dbdd".

All strings are case sensitive. They are not regex.
All strings are expected to be UTF-8 encoded.
All strings may contain any Unicode character. (no worry about composition characters or BOM mark or direction reversal etc. Assume they are all just simple printable Unicode chars.)
The size of input string may be up to 500k characters.
The expected number of replacement pairs is expected to be up to 50.
Length of each search or replacement string is anywhere from 1 char to about few thousand chars.
the algorithm used and or code speed should be reasonably efficient/fast. This function is expected to be called on 5 thousand files, each file content is considered a input string.

Write this in any lang. Emacs Lisp, Perl, Python, Ruby, JavaScript, PHP, or others. The datatype for pairs can be anything appropriate for the lang. For example, nested array/list/tuple/vector. (but don't use hash table, even if your lang preserves order.)

I'll run your program in linux, on the command line, with the linux time utility.

I'll post a solution in emacs lisp in 3 days. If no solution is given in one of the language, i'll supply one, after a week.

the langs i'll be able to run are, on linux command line:

emacs --script ‹fr.el› (24.2.1)
perl ‹fr.pl› (v5.14.2)
python ‹fr.py› (2.7.3)
python3 ‹fr.py› (3.2.3)
ruby ‹fr.rb› (1.9.3)
php ‹fr.php› (5.3.10)
node ‹fr.js› (v0.6.12) (JavaScript)