Multi-character substitution cipher algorithm

Question

My problem is the following. I have a list of substitutions, including one substitution for each letter of the alphabet, but also some substitutions for groups of more than one letter. For example, in my cipher p becomes b, l becomes w, e becomes i, but le becomes by, and ple becomes memi.

So, while I can think of a few simple/naïve ways of implementing this cipher, it's not very efficient, and I was wondering what the most efficient way to do it would be. The answer doesn't have to be in any particular language, a general structured English algorithm would be fine, but if it must be in some language I'd prefer C++ or Java or similar.

EDIT: I don't need this cipher to be decipherable, an algorithm that mapped all single letters to the letter 'w' but mapped the string 'had' to the string 'jon' instead should be ok, too (then the string "Mary had a little lamb." would become "Wwww jon w wwwwww wwww.").

I'd like the algorithm to be fully general.

Answer 1

One possible approach is to use deterministic automaton. The closest to your problem and commonly used example is Aho–Corasick string matching algorithm. The difference will be, instead of matching you would like to emit cypher at some transition. Generally at each transition you will emit or do not emit cypher. In your example

p -> b
l -> w
e -> i
le -> by
ple -> memi

The automaton (in Erlang like pseudocode)

start(p) -> p(next());
start(l) -> l(next());
start(e) -> e(next());
...

p(l) -> pl(next);
p(X) -> emit(b), start(X).

l(e) -> emit(by), start(next());
l(X) -> emit(w), start(X).

e(X) -> emit(i), start(X).

pl(e) -> emit(memi), start(next());
pl(X) -> emit(b), l(X).

If you are not familiar with Erlang, start(), p() are functions each for one state. Each line with -> is one transition and the actions follows the ->. emit() is function which emits cypher and next() is function returning next character. The X is variable for any other character.