Problem B
Triple-Free Binary Strings
Input: Standard Input
Output: Standard Output
A binary string consists of ones and zeros. Given a binary string T, if there is no binary string S such that SSS (concatenate three copies of S together) is a substring of T, we say T is triple-free. A pattern consists of ones, zeros and asterisks, where an asterisk (*) can be replaced by either one or zero. For example, the pattern 0**1 contains strings 0001, 0011, 0101, 0111, but not 1001 or 0000. Given a pattern P, how many triple-free binary strings does it contain? Input
Each line of the input represents a test case, which contains the length of pattern, n (0<n<31), and the pattern P. There can be maximum 35 test cases.
The input terminates when n=0. Output
For each test case, print the case number and the answer, as shown below.
4 0**15 *****10 **01**01**0 |
Case 1: 2Case 2: 16Case 3: 9 |
Problemsetter: Rujia Liu
Special Thanks: Shahriar Manzoor