You are given two binary strings. Find all pairs of strings such that when all s are replaced by and all s are replaced by , the two binary strings are transformed to the same final string.
For instance, if the two binary strings are and , is a valid pair.
If both binary strings begin with the same symbol, we can simply delete them and consider the remaining suffixes. We consider two cases:
- Both strings are now empty. In this case, all pairs of are valid.
- Otherwise, the starting symbols of the two strings are distinct.
In case 2, this means that is either a prefix or suffix of . WLOG, assume is a prefix of and let be the lengths of and respectively.
- If , then evidently .
- Otherwise, we can express as for some non-empty string . Substitute all s with , and our problem reduces from to .
Note that in the second case, strictly decreases so we will hit the case eventually. Working backwards, this means that both and must be periodic in .
Intuitively, the βinterlocking patternβ created when is very reminiscent of the Euclidean algorithm, which naturally leads to the periodic constraint derived above.
