Short problem statement: Given T < 200 binary strings S (|S| ≤ 105), find the size of the shortest pattern that doesn't match S for all input strings.
Examples :
S = 011101001, answer = 3 (doesnt match '000')
S = 11111, answer = 1 (doesnt match '0')
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.
