Is it the same as suffix tree?
If you are going from right most bit to left then, let k be the number of bits left:
max=fib[k+1]*max(ct1+1,ct2)
min=min(kct1+ct2,kct2+ct1)
also answer will always be less than n/2+1 so you can prune if number of differences so far exceeds that value.
I didnāt know C1(n) beforehand. In my actual solution I considered prefixes of length 19 and got C1 = 4597. That means that for a string of length 32 I would need to consider 2^12 different suffixes and for each suffix I would need to consider at most 4597 different pairs (p1,p2). In total there are 2^18=262,144 possible prefixes.
The link isnāt accessible.
Also, could you explain how you found the correct suffix?
We can build a list of the cumulative number of letters from all previous suffixes. We then use a binary search to find the first letter. The binary search will bring us to a specific suffix but is only accurate for the first letter. That is because although the suffixes are in alphabetic order, their prefixes are not. We then search in both directions to find the range of suffixes that start with that particular letter. Looking for the second letter is similar, but first we need to account for all subsequences that are just that particular letter.
1 Like
Got it, thanks! Could you update your answer to include this part as well?