Short problem statement: Given a$T<200$ binary strings $S$ $(|S| \leq 10^5)$, 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 $2^i$. When i find some k such that $matches(k) < 2^k$, this is the answer. This is $O(|S|)$ for building suffix automata plus $O(\sum_{i=1}^k 2^{i}) == O(2^{k+1})$ 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.
↵
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 $2^i$. When i find some k such that $matches(k) < 2^k$, this is the answer. This is $O(|S|)$ for building suffix automata plus $O(\sum_{i=1}^k 2^{i}) == O(2^{k+1})$ 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.
