编程介的小学生 2017-08-28 00:48 采纳率: 20.5%
浏览 666
已采纳

Dangerous Pattern

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], ..., SK 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
4

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-11 15:43
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 spring后端vue前端
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题