TopCoder problem "RepeatedPatterns" used in SRM 333 (Division I Level Two , Division II Level Three)

Problem Statement


Given are two Strings P1 and P2. Each of these strings contains a pattern of zeros and ones.

The string S(n) is formed by concatenating 1,000,000 copies of P1 followed by n copies of P2.

The infinite string S is formed by concatenating the strings S(1), S(2), S(3), ... in this order.

The string T consists of the first 10^16 characters of the string S.

We are interested in substrings of T that are zeroCount characters long and contain only zeros. Write a method that finds the first occurrence of such a substring in T, and returns the zero-based index of its first character. In case T contains no such substring return -1.



Parameters:String, String, String
Method signature:long findZeroSegment(String P1, String P2, String zeroCount)
(be sure your method is public)


-The number zeroCount may be large, and therefore it is specified as a String.


-P1 will contain between 1 and 50 characters, inclusive.
-P2 will contain between 1 and 50 characters, inclusive.
-P1 and P2 will contain only zeroes ('0') and ones ('1').
-zeroCount will contain between 1 and 17 characters, inclusive.
-zeroCount will contain only digits ('0'-'9').
-zeroCount will represent a positive integer between 1 and 10^16, inclusive.
-zeroCount will not contain leading zeros.


Returns: 7
The first occurrence of three consecutive zeroes is right in the first copy of P1.
Returns: 9999999
This time the first substring "000" starts with the last character of the 1,000,000th copy of P1.
Returns: 20000011
We have the same string T as in Example 1, only we look for the substring "00000". The first occurrence is between the second and the third copy of P2.
Returns: -1
Nowhere in the infinite string S can we find two consecutive zeroes. Clearly, in the string T there is no substring with 9876543219876 consecutive zeroes.
Returns: -1
The infinite string S does contain 9876543219876 consecutive zeroes. However, the first occurrence is too far, thus the string T doesn't contain it.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Problem categories: