Finding multiple string combinations

For an efficient solution, you can work as follows:

- declare an array of strings that is indexed by all possible character values (128 entries will do for ASCII characters); let it be Confusions;

- every entry in the array gives the list of possible confusions; the string representation such as "p|ph", "a|A"... uses a reserved separator (such as vertical bar); this allows you to specify no confusion 'x' -> "x", binary confusion 'a' -> "a|A", or multiple confusions 'o' -> "o|O|0".

- now declare a substitution function that will be called recursively. It takes on input the Nth character of the input string, and a corresponding output string; lookup the confusion string for this character and perform as many recursive calls as there are chunks in the confusion string, while appending the chunck to the current output string.

In pseudo-code:

Subsitute(int N, char In[], char Out[])
    if In[N] == '\0'
        print Out
    else
        for every Chunk in Confusion[In[N]]
            Substitue(N+1, In, Concatenete(Out, Chunk));

You will call it with

Substitue(0, In, "")

Example of what recursion will do:

(0, "pasoli", "")
    (1, "pasoli", "p")
        (2, "pasoli", "pa")
            (3, "pasoli", "pas")
                (4, "pasoli", "paso")
                    (5, "pasoli", "pasol")
                    ...
                    (5, "pasoli", "paso1")
                    ...
                (4, "pasoli", "pasO")
                    (5, "pasoli", "pasOl")
                    ...
                    (5, "pasoli", "pasO1")
                    ...
                (4, "pasoli", "pas0")
                    (5, "pasoli", "pas0l")
                    ...
                    (5, "pasoli", "pas01")
                    ...
        (2, "pasoli", "pA")
        ...
    (1, "pasoli", "ph")
    ....

Here is Python code that does it (sorry, not C):

Confusions= { "p": ["p", "ph"], "a": ["a", "A"], "o": ["o", "O", "0"], "l": ["l", "1"], "i": ["i", "1"] }

def Substitute(N, In, Out):
    if N == len(In):
        # Done with the input string
        print Out
    else:
        if In[N] in Confusions:
            # Substitute every chunk
            for Chunk in Confusions[In[N]]:
                Substitute(N + 1, In, Out + Chunk)
        else:
            # No rule for this letter, treat as a chunk
            Substitute(N + 1, In, Out + In[N])
         
   
Substitute(0, "pasoli", "")

pasoli
pasol1
paso1i
paso11
pasOli
pasOl1
pasO1i
pasO11
pas0li
pas0l1
pas01i
pas011
pAsoli
pAsol1
pAso1i
pAso11
pAsOli
pAsOl1
pAsO1i
pAsO11
pAs0li
pAs0l1
pAs01i
pAs011
phasoli
phasol1
phaso1i
phaso11
phasOli
phasOl1
phasO1i
phasO11
phas0li
phas0l1
phas01i
phas011
phAsoli
phAsol1
phAso1i
phAso11
phAsOli
phAsOl1
phAsO1i
phAsO11
phAs0li
phAs0l1
phAs01i
phAs011