SuspiciousStrings
SRM 283 · 2006-01-19 · by gevak
Problem Statement
You work at a company specializing in internet-related technologies, and your current project is a spam filter. This filter determines whether or not a string contains spam-like information using a "spam-words-dictionary" (SWD). If an input string contains at least one word from this dictionary as a substring, the filter considers it to be spam-suspicious. (Note: an entire string is considered a substring of itself.)
You've decided to solve a more challenging problem: how many unique strings of length n, composed entirely of lowercase letters, are spam-suspicious for a given SWD? You are given a
Notes
- "Substring" is formed of consecutive letters (so, it's NOT a subsequence of letters).
- "x modulo y" means the remainder of x divided by y.
Constraints
- dictionary will contain between 1 and 10 elements, inclusive.
- Each element of dictionary will contatin only lowercase letters ('a'-'z').
- Each element of dictionary will contain between 1 and 10 characters, inclusive.
- n will be between 1 and 2147483647, inclusive.
{"x"}
1
Returns: 1
All one character length strings are allowed except for "x".
{"ab","bb"}
2
Returns: 2
Suspicious strings are "ab" and "bb".
{"ab","bb"}
5
Returns: 6350
{"aab","bba"}
5
Returns: 4054
{"xxxxxx","xxx","x","yyxyy","xxxyxxx","y","yx","xy","zzzzzzzzzz"}
5
Returns: 8752
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SuspiciousStrings with a public method int getAmount(vector<string> dictionary, int n) · 81 test cases · 2 s / 256 MB per case