Two bit streams are given, differing from each other by no more than k bits.

How to ignore minor distortions, and find these threads the same?

Closed due to the fact that the essence of the issue is not clear to the participants of Oleksii Shapovalov , dizballanze , Pavel Mayorov , m0nhawk , Alexey Shtanko Jun 15 '15 at 21:29 .

Try to write more detailed questions. To get an answer, explain what exactly you see the problem, how to reproduce it, what you want to get as a result, etc. Give an example that clearly demonstrates the problem. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • What are the sequences given? What does it mean that they differ in k bits? Are the sequences sorted or not? - Vlad from Moscow
  • bit sequences. same except for k bits - Jonathan Livingston
  • What is a "bit sequence"? How do you define it in C ++? In this case, it is not clear whether they have the same length or not? This is most likely a question not on C ++, but on algorithms. - Vlad from Moscow
  • one
    Compare bit by bit, and if there are k + 1 pairs of unequal bits, then the sequences should be considered unequal - Ni55aN
  • Are different lengths of threads valid? In any case, compare bitwise. After the first difference found, the “greedy” search for the longest identical pieces in the remaining tails begins: what is considered an error and in which of the streams in order to maximize the coincidences. This is probably an NP-complete task. - Sergiks

1 answer 1

Well, what's the difficulty? Here is a sketch:

unsigned int bit_count(unsigned int v) // Kerrighan way { unsigned int accum; for (accum = 0; v; accum++) v &= v - 1; return accum; } bool compare(seq s1, seq s2, unsigned int ignore_bits) { unsigned int rest_bits = ignore_bits; while (!s1.finished() || s2.finished()) { unsigned int curr1 = s1.current_int(), curr2 = s2.current_int(); unsigned int diff = curr1 ^ curr2; unsigned int different_bits = bit_count(diff); if (different_bits > rest_bits) return false; rest_bits -= different_bits; } return s1.finished() && s2.finished(); } 

The solution may differ depending on how you want to interpret sequences of different lengths. Throw tail? To count missing bits as zeros? To consider missing bits as mismatched?


The solution uses an undefined seq type representing the bit sequence. If you specify your type, you can also clarify the solution.

  • one
    @PavelMayorov: Well, the question sounded unequivocally: Two bit streams are given . Anti-noise coding is “given ONE stream”. - VladD
  • one
    @VladD, as I understand it, this solution can only compare strings of the same length? In fact, we are looking at the difference that occurs when a bit is replaced and completely ignores insert-delete. In principle, I thought that here it is possible to look differently, i.e. as in the diff utility. But, of course, the task is completely vaguely formulated. - avp
  • one
    @avp: Yeah, diff has a much more difficult task. He probably appreciates the dissimilarity of the lines, and when he is too large he begins to look forward. - VladD
  • one
    @VladD, in the wiki, they write that diff is based on finding the greatest common sequence to which then the delete and insert operations are applied. - avp
  • one
    @avp: And apparently the most algorithmically difficult part is finding the largest subsequence . - VladD