查找多个字符串组合 [英] Finding multiple string combinations

问题描述

我需要这里社区的帮助.我的问题如下:

我有一些字符串数组，例如

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...

上面的数组显示了每个数组的困惑.现在，我必须将原始字符串"pasoli"构建为多个字符串，例如

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...

这里将使用以下所有不同形式的字符串:对于"p"，我们可以使用"p"或"ph"，对于"a"，我们可以使用"a"或一个''.这样，我们必须继续替换并找到字符串.

"patal"为"phatal"或"pAtal"或"pathal"等


非常感谢您的帮助.

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.

推荐答案

要获得有效的解决方案，您可以按以下方式工作:

-声明由所有可能的字符值索引的字符串数组(对于ASCII字符，将有128个条目)；设为Confusions;

-数组中的每个条目都列出了可能造成混淆的列表；字符串表示形式，例如"p|ph"，"a|A" ...使用保留的分隔符(例如竖线)；这使您可以指定无混淆的''x''-> "x"，二进制混淆''a''-> "a|A"，或多次混淆''o''-> "o|O|0".

-现在声明一个将递归调用的替换函数.它接受输入字符串的第N个字符和相应的输出字符串；查找此字符的混淆字符串，并执行与混淆字符串中的块一样多的递归调用，同时将块添加到当前输出字符串中.

用伪代码:

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")
    ....

这是执行此操作的Python代码(对不起，不是C):

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

这篇关于查找多个字符串组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！