NonDeterministicSubstring
SRM 689 · 2016-04-01 · by cgy4ever
Problem Statement
A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining.
Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A.
Constraints
- A will contain between 1 and 50 characters, inclusive.
- B will contain between 1 and 50 characters, inclusive.
- Each character in A will be '0' or '1'.
- Each character in B will be '0', '1' or '?'.
"00010001" "??" Returns: 3
There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
"00000000" "??0??0" Returns: 1
There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
"001010101100010111010" "???" Returns: 8
Each of the 8 strings that match B occurs somewhere in A.
"00101" "??????" Returns: 0
Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
"1101010101111010101011111111110001010101" "???????????????????????????????????" Returns: 6
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NonDeterministicSubstring with a public method long long ways(string A, string B) · 67 test cases · 2 s / 256 MB per case