CharacterBoard | Topcoder Archive

Problem Statement

Manao has a matrix X with 1,000,000,000 rows and W columns. He likes to fill it with characters; he even has developed an algorithm for this task. First, he chooses a string S consisting of at most W lowercase letters. The string S is called the generator. Then, he applies the algorithm described by the following pseudocode:

cur := 0
for i := 0 to 999999999
  for j := 0 to W - 1
    X[i][j] := S.charAt(cur)
    cur := (cur + 1) mod length(S)

Manao has recently found a matrix X in his notepad. He wonders whether it was generated using the above algorithm. You are given:

a String[] fragment that contains a rectangular submatrix of X,
the int W: the width of X,
and two ints i0 and j0: the coordinates of the upper left corner of your submatrix within X.

In other words, for all valid i, j we have fragment[i][j] = X[i + i0][j + j0]. Count how many different generators Manao could have used to create a matrix X that contains the fragment you were given. Return this number modulo 1,000,000,009.

Definition

Class:: CharacterBoard
Method:: countGenerators
Parameters:: String[], int, int, int
Returns:: int
Method signature:: int countGenerators(String[] fragment, int W, int i0, int j0)
(be sure your method is public)

Constraints

fragment will contain N elements, where N is between 1 and 10, inclusive.
Each element of fragment will be M characters long, where M is between 1 and 10, inclusive.
Each element of fragment will consist of lowercase letters ('a'-'z') only.
W will be between M and 1,000,000,000, inclusive.
i0 will be between 0 and 1,000,000,000 - N, inclusive.
j0 will be between 0 and W - M, inclusive.

Examples

```
{"dea",
 "abc"}
```
```
7
```
```
1
```
```
1
```
```
Returns: 1
```
Manao has a matrix with 1000000000 rows and 7 columns. We know that it looks as follows: ??????? ?dea??? ?abc??? ??????? ... The only string of length at most 7 which could generate such matrix is "abcde".
```
{"xyxxy"}
```
```
6
```
```
1
```
```
0
```
```
Returns: 28
```
The given information is: ?????? xyxxy? ?????? ... The corresponding generator could be "xyx", "yxyxx", or a string of form "xyxxy?", where '?' stands for any lowercase letter.
```
{"gogogo",
 "jijiji",
 "rarara"}
```
```
6
```
```
0
```
```
0
```
```
Returns: 0
```
No generator could create this matrix using the given algorithm.

{"abababacac",
 "aaacacacbb",
 "ccabababab"}

Returns: 829146844

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.