BadSubstrings
TCCC05 Finals · 2005-01-10 · by vorthys
Problem Statement
Consider strings constructed from the letters 'A', 'B', and 'C'. You will be given an integer N and two forbidden substrings, bad1 and bad2. You are to calculate the number of strings of length N that do not contain either substring. Note that a substring need not be shorter than the string in which it is contained (e.g., "AB" is a substring of "AB").
Constraints
- N is between 1 and 39, inclusive.
- bad1 contains between 1 and 39 characters, inclusive.
- bad2 contains between 1 and 39 characters, inclusive.
- Each character in bad1 is 'A', 'B', or 'C'.
- Each character in bad2 is 'A', 'B', or 'C'.
3 "AB" "BA" Returns: 17
There are 17 three-letter strings that do not contain "AB" or "BA", shown below: AAA AAC ACA ACB ACC BBB BBC BCA BCB BCC CAA CAC CBB CBC CCA CCB CCC
2 "A" "BB" Returns: 3
5 "ABC" "ABB" Returns: 189
39 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" "ABCABCABCABCABCABCABCABCABCABCABCABCABC" Returns: 4052555153018976265
39 "ABCABCABCABCABCABCABC" "ABCABCABCABCABCABCABB" Returns: 4052555138756162709
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BadSubstrings with a public method long long howMany(int N, string bad1, string bad2) · 76 test cases · 2 s / 256 MB per case