Short problem statement: Given $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.↵
↵
EDIT : Came up with a better solution, but still TLE:↵
↵
Run BFS in suffix automata starting from root node until we find some node that has less than 2 links. Let p be the length of the path from root to this node. This node represents some suffix of length p+1 that doesn't appear in the string $S$. So the answer is p+1.
↵
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.↵
↵
EDIT : Came up with a better solution, but still TLE:↵
↵
Run BFS in suffix automata starting from root node until we find some node that has less than 2 links. Let p be the length of the path from root to this node. This node represents some suffix of length p+1 that doesn't appear in the string $S$. So the answer is p+1.
