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.

 

Definition

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

Notes

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

Constraints

-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.
 

Examples

0)
    
"111010100001010"
"010000001000"
"3"
Returns: 7
The first occurrence of three consecutive zeroes is right in the first copy of P1.
1)
    
"1101010010"
"0001000"
"3"
Returns: 9999999
This time the first substring "000" starts with the last character of the 1,000,000th copy of P1.
2)
    
"1101010010"
"0001000"
"5"
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.
3)
    
"10101010"
"101010101010"
"9876543219876"
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.
4)
    
"11111111111111111111111111"
"0"
"9876543219876"
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:

http://www.topcoder.com/stat?c=problem_statement&pm=7294

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10657&pm=7294

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Problem categories:

Greedy