StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've done it a number of times. The way I do it is with a recursive depth-first tree-walk of the game tree of possible changes. There is a budget <em>k</em> of changes, that I use to prune the tree. With that routine in hand, first I run it with k=0, then k=1, then k=2 until I either get a hit or I don't want to go any higher.</p> <pre class="lang-cpp prettyprint-override"><code>char* a = /* string 1 */; char* b = /* string 2 */; int na = strlen(a); int nb = strlen(b); bool walk(int ia, int ib, int k){ /* if the budget is exhausted, prune the search */ if (k < 0) return false; /* if at end of both strings we have a match */ if (ia == na && ib == nb) return true; /* if the first characters match, continue walking with no reduction in budget */ if (ia < na && ib < nb && a[ia] == b[ib] && walk(ia+1, ib+1, k)) return true; /* if the first characters don't match, assume there is a 1-character replacement */ if (ia < na && ib < nb && a[ia] != b[ib] && walk(ia+1, ib+1, k-1)) return true; /* try assuming there is an extra character in a */ if (ia < na && walk(ia+1, ib, k-1)) return true; /* try assuming there is an extra character in b */ if (ib < nb && walk(ia, ib+1, k-1)) return true; /* if none of those worked, I give up */ return false; } </code></pre> <p>Added to explain trie-search:</p> <pre class="lang-cpp prettyprint-override"><code>// definition of trie-node: struct TNode { TNode* pa[128]; // for each possible character, pointer to subnode }; // simple trie-walk of a node // key is the input word, answer is the output word, // i is the character position, and hdis is the hamming distance. void walk(TNode* p, char key[], char answer[], int i, int hdis){ // If this is the end of a word in the trie, it is marked as // having something non-null under the '\0' entry of the trie. if (p->pa[0] != null){ if (key[i] == '\0') printf("answer = %s, hdis = %d\n", answer, hdis); } // for every actual subnode of the trie for(char c = 1; c < 128; c++){ // if it is a real subnode if (p->pa[c] != null){ // keep track of the answer word represented by the trie answer[i] = c; answer[i+1] = '\0'; // and walk that subnode // If the answer disagrees with the key, increment the hamming distance walk(p->pa[c], key, answer, i+1, (answer[i]==key[i] ? hdis : hdis+1)); } } } // Note: you have to edit this to handle short keys. // Simplest is to just append a lot of '\0' bytes to the key. </code></pre> <p>Now, to limit it to a budget, just refuse to descend if hdis is too large.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload