Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C Algorithms
i need help from the community here. My problem is as follows:
 
I have some string arrays like
arr1[][]="p","ph"; are the confusions for 'p'
arr2[][]="a","A"; are the confusions for 'p'
arr3[][]="s',"sh"; are the confusions for 's'
arr4[][]="o","O"; are the confusions for 'o'
arr5[][]="l","n"; are the confusions for 'l'
arr6[][]="i","I"; are the confusions for 'i'
etc...
the above arrays shows the confusions for each of them. Now I have to build the original string "pasoli" as multiple strings like
pasoli
phasoli
pAsoli
phAsoli
pasholi
pAsholi 
etc...
Here all the different forms of strings to be generated by using: for 'p' we can have 'p' or 'ph', for 'a' we have 'a' or 'A'. This way we have to go on substituting and find the string.
 
"patal" as "phatal" or "pAtal" or "pathal" etc
 

Any help is greatly appreciated, thanks.
Posted 12-Apr-12 0:46am
Edited 12-Apr-12 0:56am
Slacker00775.8K
v2
Comments
Slacker007 at 12-Apr-12 5:56am
   
Edited for readability and formatting.

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

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
  Permalink  
v4
Comments
Sandeep Mewara at 23-Apr-12 11:01am
   
My 5!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 450
1 OriginalGriff 230
2 DamithSL 150
3 Dave Kreskowiak 120
4 Suvendu Shekhar Giri 110
0 OriginalGriff 7,740
1 DamithSL 5,644
2 Sergey Alexandrovich Kryukov 5,404
3 Maciej Los 5,011
4 Kornfeld Eliyahu Peter 4,539


Advertise | Privacy | Mobile
Web03 | 2.8.141223.1 | Last Updated 23 Apr 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100