NonDeterministicSubstring | Topcoder Archive

Problem Statement

You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'.

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.

Definition

Class:: NonDeterministicSubstring
Method:: ways
Parameters:: String, String
Returns:: long
Method signature:: long ways(String A, String B)
(be sure your method is public)

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

Examples

```
"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

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.