PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Koulick Sadhu
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra
DIFFICULTY:
3015
PREREQUISITES:
Strings
PROBLEM:
You are given two binary strings A and B, each of length N.
Consider a non-empty substring A' of A and a non-empty substring B' of B, both of the same length. Let X = A' \oplus B' be the string obtained by taking the exclusive OR of A' and B'.
You are also given a function f(X), defined as
where |X| denotes the length of X and X_{10} denotes the decimal value of the binary integer represented by X. For example, if X = 0110101, then |X| = 7 and X_{10} = 53, so f(X) = \lfloor 7 / 2^{53} \rfloor = 0.
Your task is to maximize the value of the function f(X) for the given strings A and B, by choosing A' and B' appropriately.
Note: The exclusive OR of two binary strings A and B such that |A| = |B| = k is the unique binary string X of length k such that X_i = 1 if and only if A_i \neq B_i.
QUICK EXPLANATION:
In order to maximise the profit, we need to minimise the value of XOR as profit is inversely proportional to the XOR value. Also we need to maximise the length of the substring.
Therefore we just need to find the longest common substrings from both the strings S and Q as their XOR would be 0 and the length would be maximum. This would make the answer as |X|.
If there are no such substring, then the answer would always be 0
TIME COMPLEXITY:
O(NlogN) for each test case.