Need help with string matching problem
Разница между en1 и en2, 139 символ(ов) изменены
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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский skavurskaa 2016-06-15 23:48:11 13 Tiny change: 'ents some suffix of length' -> 'ents some pattern of length'
en4 Английский skavurskaa 2016-06-15 03:18:44 166
en3 Английский skavurskaa 2016-06-15 03:13:14 327
en2 Английский skavurskaa 2016-06-15 02:58:26 139 add examples
en1 Английский skavurskaa 2016-06-15 02:56:27 668 Initial revision (published)