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.