Short problem statement: Given a binary string S (|S| ≤ 105), find the size of the shortest pattern that doesn't match S.
My current solution is building a suffix automaton for S and searching all patterns of size i (i=1, i=2, ...) while the number of matches of this size equals 2i. When i find some k such that matches(k) < 2k, this is the answer. This is O(|S|) for building suffix automata plus 
for matchings, which i think is always small but still relevant.
This solution gets TLE. Can anyone help me with a faster solution for this problem? Thanks in advance.
