2 shunfurh shunfurh 于 2017.08.31 17:23 提问

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个回答

caozhy
caozhy   Ds   Rxr 2017.09.15 23:46
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
单例解析-Double-checked locking and the Singleton pattern
Level: IntermediatePeter Haggar (haggar@us.ibm.com), Senior Software Engineer, IBM 01 May 2002All programming languages have their share of idioms. Many are useful to know and use, and programme
Error: Running Homebrew as root is extremely dangerous and no longer supported.
homebrew 无法安装,提示不能在根目录下使用BUG: Error: Running Homebrew as root is extremely dangerous and no longer supported. As Homebrew does not drop privileges on installation you would be giving all build scripts
discuz ASP.NET 4.0验证请求 A potentially dangerous Request.Form value was detected from the client
服务器系统使用Windows 2003,ASP.NET 4.0,Discuz.Net版本 发表新贴子报错如下: Server Error in '/' Application. A potentially dangerous Request.Form value was detected from the client (topicsubmit="发表帖子"). Description
Android 6.0 Dangerous Permissions与授权机制
android 6.0 Marshmallow版本之后,系统不会在软件安装的时候就赋予该app所有其申请的权限,对于一些危险级别的权限,app需要在运行时一个一个询问用户授予权限。 From android M permissions will be granted at runtime. User consent is not required for Normal permissions b
A potentially dangerous Request.Path value was detected from the client异常解决方案
场景: 当URL中存在“,*,%,&,:,/”特殊字符时,页面会抛出A potentially dangerous Request.Path value was detected from the client异常。   原因: 是ASP.NET默认的拦截机制,保证页面URL传输的一定安全性。   解决方案有两种: 第一种,直接去除页面请求危险字符验证:
Android6.0极其以上系统获取Dangerous系统权限问题及其解决方案
开发过程当中遇到一个问题,就是好好的app在Android6.0系统的五儿子里进去就闪退,看了一下logcat表明时WRITE_EXTERNAL_STORAGE权限获取不到造成的,but在AndroidManifest文件当中已经添加了该权限,只能猜测在6.0的机子上无法使用配置文件中的权限了,于是去setting里面把application的权限手动开启试了一下,app就正常了。因此去趴了Andr
ASP.net 4.0嵌入Ckeditor 3.5 报错A potentially dangerous Request.Form value was detected from the client 的解决办法
<br />新发布的版本Ckeditor3.5 嵌入到 ASP.net 4.0 页面时报错如下:<br /><br />--------------------------------------------------------------------------------<br /><br />Server Error in '/' Application. <br />-----------------------------------------------------------------
Archlinux(PC机)安装实时内核 linux-rf-bfq和linux-rt
首先保证机器上已安装 AUR助手,否则就得手动下载包安装。我这里用的是 yaourt。 实时内核linux-rt-bfq来源于网址:https://aur.archlinux.org/packages/linux-rt 1.输入命令 $ yaourt -S linux-rt-bfq 2.提示 "unsupported package: potentially dangerous !“,
错误解决:[A potentially dangerous Request.Form value was detected from the client (warning="卡Ć.
N:\PSA PEUGEOT\2012\02\20120214-Liduoduo\source\Répartition 120214.xls是这个路径的问题 é是这个路径 一.vs.net在新建工程时弹出"Automation 服务器不能创建对象"的解决方案 原因是FileSystemObject创建失败的问题, 解决的方法:运行Regsvr32 scrrun.dll 二.
warning: the ‘gets' function is dangerous and should not be used
今天在LINUX下编译C程序时,出现了: warning: the 'gets' function is dangerous and should not be used. 这样的一个警告,在经过查阅资料以及自己的努力之后,才得知问题出在程序中使用了 gets  ,Linux 下gcc编译器不支持这个函数,解决办法是使用 fgets,同时对程序做稍微的修改即可. [cpp]