Need help with string matching problem
Difference between en4 and en5, changed 13 character(s)
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 2: Solved the problem using the strategy below. I will leave the blog here any way because this problem looks interesting so i want to share the solution in case any one is interested :)↵

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 
suffixpattern of length p+1 that doesn't appear in the string $S$. So the answer is p+1.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English skavurskaa 2016-06-15 23:48:11 13 Tiny change: 'ents some suffix of length' -> 'ents some pattern of length'
en4 English skavurskaa 2016-06-15 03:18:44 166
en3 English skavurskaa 2016-06-15 03:13:14 327
en2 English skavurskaa 2016-06-15 02:58:26 139 add examples
en1 English skavurskaa 2016-06-15 02:56:27 668 Initial revision (published)