RepeatedPatterns | Topcoder Archive

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

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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.