0
$\begingroup$

I need to write a function that gets an array of bytes at the input and 2 integers (minDist and maxDist). The calculation algorithm understands this field as a bit sequence starting from the LSB (least significant bit) of the first byte and ending with the MSB (the most significant bit) of the last byte. Therefore, for the input of the length of n bytes, we have a sequence of 8n bits. The task is to test all non-empty prefixes (prefixes) of this bit sequence and all non-empty suffixes of this sequence, for each pair (prefix x suffix), you need to specify their editing distance. The result is the number of pairs whose editing distance belongs to the specified closed interval . The editing distance of a pair of bit strings is the smallest number of bit deletions / insertions / bit changes so that from one bit string we get another one.

I would use Levenshtein's algorithm (https://rosettacode.org/wiki/Levenshtein_distance#C.2B.2B ) with adjustments, which I think would work?

Since prefixes and suffixes altogether sum to 8*n (n is the number of bytes of the problem, we do not test the empty string), the problem can be resolved by testing 64*n^2 string pairs, each comparison consuming n^2 operations. Thus, in total, solving one problem, the function has the complexity of n^4, by appropriate modification the complexity can be reduced to n^3.

If I understand correctly, if I used Levenshtein algorithm I will get complexity of n^4, but how do I go on modifying to n^3?

Maybe I'm completely mistaken, please correct me.

$\endgroup$
  • 3
    $\begingroup$ (You keep getting the spelling of Levenshtein wrong, starting from the title.) The editing distance from one "fixed" string to a second isn't that much different from that to the same string with one character less (or more) at the beginning (or end). $\endgroup$ – greybeard Mar 17 '18 at 20:27
  • $\begingroup$ @greybeard To be fair, can you spell Levenshtein correctly without looking it up? I can't. $\endgroup$ – Discrete lizard Mar 18 '18 at 9:20
  • $\begingroup$ (@Discretelizard: Coincidentally, I can - due to my "native tongue" being at least close to the one where the transliteration from Löwenstein to Levenshtein started (and basic knowledge of English pronunciation. And having seen Levenshtein before). Then again, it is spelled conventionally in the links.) $\endgroup$ – greybeard Mar 18 '18 at 10:58
  • $\begingroup$ (@greybeard Well, I think my own native tongue is pretty close as well, but Levensthein seems a lot more natural to me) $\endgroup$ – Discrete lizard Mar 18 '18 at 11:10
  • $\begingroup$ Where did you encounter this problem? Can you edit the question to credit the source? Thanks! $\endgroup$ – D.W. Mar 18 '18 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.