Dangerous Pattern
Time Limit: 2 Seconds Memory Limit: 32768 KB
The FBI has just now got the information that the terrorists are machinating
a new terroristic attack. The terrorists keep contact in some magazines, newspapers,
in some crypto ways. We will say a section of text contains dangerous pattern
if S[1], S[2], ..., S[K] (S[1], S[2], ... S[K] is given to you) appears in the
specified order and does not overlap.
For example if we have
K = 2
S[1] = 'aa'
S[2] = 'ab'
the text 'aaab' contains a dangerous pattern but the text 'aab' does not. Because
the appearance of 'aa' (position [1, 2]) and the appearance of 'ab' (position
[2, 3]) overlaps. Neither does 'abaa' because the appearance of them ([3, 4]
and [1, 2]) are not in the specified order.
Now it turns to you the task to count how many different dangerous patterns
a given text contains. We will say that two dangerous patterns are different
when and only when there is at least S[i] such that the appearance of S[i] in
this two patterns differs.
For example, if
K = 2
S[1] = 'a'
S[2] = 'b'
text = 'aabb'
There are four different dangerous patterns in this text ([1, 3], [1, 4], [2,
3], [2, 4] represented by the position of the appearance.
The result may be too large, you need only to output the remainder that the
result divides 28851.
Some constraints for this problem:
1. The total length of the S[i] does not exceed 10,000.
2. For all the string S[1], S[2], ..., S[K], there are no two string S[i] and
S[j] such that S[i] is the suffix of S[j].
3. The total length of the text does not exceed 500,000.
4. The character that appears in S[i] or in the text are all latin letters in
lowercases. (i.e. 'a' .. 'z')
Input
The first line of the input is a single number X (0 < X <= 10), the number
of the test cases of the input. Then X blocks each represents a single test
case.
For each block the first line is an integer K. Then K lines, the (i+1)-th lines
represents S[i]. Then one line whose length does not exceed 500,000 represents
the text.
There're NO breakline between two continuous test cases.
Output
For each block output one line that is the remainder that the number of different dangerous patterns divides 28851.
Sample Input
2 2 a b aabb 2 a b aabb
Sample Output
4 4Submit
Source: Online Contest of Christopher's Adventure