SuspiciousStrings | Topcoder Archive

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 String[] dictionary, each element of which is a word from the SWD, and an int n. Return the answer modulo 10000.

Definition

Class:: SuspiciousStrings
Method:: getAmount
Parameters:: String[], int
Returns:: int
Method signature:: int getAmount(String[] dictionary, int n)
(be sure your method is public)

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.

Examples

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

Returns: 8752

{"aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee",
 "ffffffffff", "gggggggggg", "hhhhhhhhhh", "xxxxxxxxxx", "zzzzzzzzzz"}

2147483647

Returns: 5040

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.