RepeatedPatterns
SRM 333 · 2007-01-04 · by misof
Problem Statement
Given are two
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.
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.
"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.
Submissions are judged against all 135 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RepeatedPatterns with a public method long long findZeroSegment(string P1, string P2, string zeroCount) · 135 test cases · 2 s / 256 MB per case