查找多个字符串组合

本文介绍了查找多个字符串组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要这里社区的帮助.我的问题如下: 我有一些字符串数组，例如

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