StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POString distance, transpositions only
text
Body
copied!<blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="https://stackoverflow.com/questions/7797540/counting-the-swaps-required-to-convert-one-permutation-into-another">Counting the swaps required to convert one permutation into another</a> </p> </blockquote> <p>I'm looking for an algorithm that would count some kind of string distance where only allowed operation is transposition of two adjacent characters. For example: <br /> string1: "mother" <br /> string2: "moterh" <br /> distance: 2 (first swap "h" with "e" and get "motehr" and then "h" with "r" resulting in "moterh") <br /> I know that Damerau–Levenshtein distance is quite alike that problem however it requires a lot of memory (I'd like it to work quite fast on words up to 1 000 000 characters). I've already written this:</p> <pre><code>int amo = 0; for (int i = 0; i < n; i++) { if (fromString[i] == toString[i]) continue; char toWhat = toString[i]; int where = -1; for (int j = i; j < n; j++) { if (fromString[j] == toWhat) { where = j; break; } } while (where != i) { char temp = fromString[where]; fromString[where] = fromString[where - 1]; fromString[where - 1] = temp; where--; amo++; } } cout << amo << endl;` </code></pre> <p>Strings are represented as char[n] where n is their length. I'm quite sure there's a way to do it faster and I'd be very thankful if somebody will tell me how to do it or write some source code (best would be Java/Python/C++ but anything's be great).</p> <p>P.S. Excuse me any language mistakes, I'm not English and I haven't mastered that language yet.</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