Smallest possible reader problem

[fiveworlds]

Suppose I want to change a string from left to right

 

001001 to 000010

010010 to 000100

Etc.

 

In one pass is there any way to work out the minimum number of bits I would have to read at one time?

 

At first glance it appears I could use the levenstein distance but that wouldn't find the most optimal solution.

Edited May 3, 2017 by fiveworlds

[Strange]

I think you have to have enough storage for the entire bit-string. You can't start putting out the reversed string until you see the end of it.

[fiveworlds]

Well at worst you would need enough storage for the whole string. However say my string was composed of regular expressions. The largest reader I would need would be the size of the largest regular expression. For instance

 

0010010010010011001101

 

Is 2 regular expressions 001 and 1001101 so the largest reader I would need would be of size 7.

 

Also it should make use of don't care terms eg

 

1001 to 1010 should only require a regular expression of size 3 since we don't care what the second term is.

Edited May 3, 2017 by fiveworlds