I am recently faced with the following problem. You are given binary string a and b where 1 <= length(a) <= length(b) <= 10^5. Let length(a) = n. Now we are required to find the smallest binary-valued substring S of b with length n where XOR(S, a) is minimum. I thought a solution with bitsets which may avoid TL, but i couldn't made it up. Can anybody help me to solve this, please?
Example: Input: 1101 1011000 Output: 1100
Let's first solve it with O(n3) greedy. Let's construct answer from highest bit to lowest, setting it at first to a[i] and if it's not possible to construct answer with such prefix, change it to a[i] ^ 1. How can we check if it's possible to construct answer with given prefix? Let's find rightest occurence as a substring of ourPrefix^prefixOfA and check that it's far enough from end of string. To speed up this solution you can use suffix arrray or suffix tree or hashing to find rightest occurence faster.