Need help with string matching problem

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Short problem statement: Given T < 200 binary strings S (|S| ≤ 10⁵), 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ⁱ. When i find some k such that matches(k) < 2^k, this is the answer. This is O(|S|) for building suffix automata plus $\text{[math]}$ 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 pattern of length p+1 that doesn't appear in the string S. So the answer is p+1.

Comments (9)

Write comment?

skavurskaa

8 years ago, # |

Auto comment: topic has been updated by skavurskaa (previous revision, new revision, compare).

→ Reply

Branimir

Can you share the link of the problem?, please. I think that I can solve the problem more easily(without suffix automaton).

8 years ago, # ^ |

URI Online Judge (single test case per file even though problem statement says otherwise): http://www.urionlinejudge.com.br/judge/en/problems/view/2093

Also in spoj (T<200 tests per file): http://spoj.com/problems/TAP2013E/

bicsi

← Rev. 3 →

If you analyze the problem more thoroughly, you may observe the interesting fact that the length of the solution callot exceed ⌈ log(L)⌉ (why?). This way you can solve the problem much more easily (albeit in a "worse" time bound of O(L * log(L))).

Edit: Also, keep in mind that if you want to keep track of strings of small length, you can as well use a simpler "Rabin Karp" approach (hashing).

I had this feeling that the answer could never be too big! That's why my first idea was testing all small patterns using suffix automaton pattern matching utility. Unfortunately it got TLE. Maybe a simpler approach like yours, which doesn't build the SA, can pass in the time limits.

Thanks for the contribution

Dhruv_Gheewala

4 years ago, # ^ |

← Rev. 2 →

can we do it by binary-search + Bruteforce(to generate all binary string of particular length) + Rabin-Karp(to find a match)? but it has high time complexity which will not pass in given constraints. can you suggest any better way?

skavurskaa's blog