How can we write an efficient function that outputs "[homoglyph equivalents][1]" of an input string? **Example 1** (pseudo-code): homoglyphs_list = [ ["o", "0"], // "o" and "0" are homoglyphs ["i", "l", "1"] // "i" and "l" and "1" are homoglyphs ] input_string = "someinput" output = [ "someinput", "s0meinput", "somelnput", "s0melnput", "some1nput", "s0me1nput" ] **Example 2**: homoglyphs_list = [ ["rn", "m", "nn"], ] input_string = "rnn" output = ["rnn", "rm", "mn", "rrn", "nnn", "nm", "nrn"] **Example 3**: homoglyphs_list = [ ["d", "ci", "a"], // "o" and "0" are homoglyphs ["i", "l", "1"] // "i" and "l" and "1" are homoglyphs ] /* notice that with the two rules above, we can infer "d" = "ci" = "a" = "cl" = "c1" */ input_string = "pacerier" output = [ "pacerier", "pacerler", "pacer1er", "pcicerier", "pcicerler", "pcicer1er", "pclcerier", "pc1cerier", "pclcerler", "pc1cerler", "pclcer1er", "pc1cer1er", "pdcerier", "pdcerler", "pdcer1er" ] Note: The order of the members in the output array isn't important, and we can assume that the given homoglyph mappings are assumed to be *proper* (inputs wouldn't give us an "infinite loop"). My current algorithm works, but it's using raw bruteforcing and performance is awful. E.g. an input of `"mmmmm"` with homoglyphs `["rn", "m", "nn"]` takes 38 seconds to run: // This is php code (non-pseudo just so we could test the running time), // but the question remains language-agnostic public function Func($in, Array $mappings){ $out_table = array(); $out_table[$in] = null; while(true){ $number_of_entries_so_far = count($out_table); foreach(array_keys($out_table) as $key){ foreach($mappings as $mapping){ foreach($mapping as $value){ for($a=0, $aa=strlen($key); $a<$aa; ++$a){ $pos = strpos($key, $value, $a); if($pos === false){ continue; } foreach($mapping as $equal_value){ if($value === $equal_value){ continue; } $out_table[substr($key, 0, $pos) . $equal_value . substr($key, $pos + strlen($value))] = null; } } } } } if($number_of_entries_so_far === count($out_table)){ // it means we have tried bruteforcing but added no additional entries, // so we can quit now break; } } return array_keys($out_table); } How can we implement an efficient (fast) homoglyph expansion algorithm? [1]: https://en.wikipedia.org/wiki/Homoglyph#Zero_and_O.3B_one.2C_l_and_I
And what it will do if I write like $homoglyph_mappings[0] = array("n", "nn" , "nnn"); ??