Problem 1943 --Ucloud的安全密钥(困难)

1943: Ucloud的安全密钥(困难)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
 

每个 UCloud 用户会构造一个由数字序列组成的秘钥,用于对服务器进行各种操作。作为一家安全可信的云计算平台,秘钥的安全性至关重要。因此,UCloud 每年会对用户的秘钥进行安全性评估,具体的评估方法如下:

首先,定义两个由数字序列组成的秘钥 a  b 近似匹配( 的关系。a  b 近似匹配当且仅当同时满足以下两个条件:

  • |a|=|b|a=b,即 aa 串和 bb 串长度相等。
  • 对于每种数字 cccc  aa 中出现的次数等于 cc  bb 中出现的次数。

此时,我们就称 a  b 近似匹配,即 ab。例如, (1,3,1,1,2)≈(2,1,3,1,1)

UCloud 每年会收集若干不安全秘钥,这些秘钥组成了不安全秘钥集合 T。对于一个秘钥 ss 和集合 T 中的秘钥 t 来说,它们的相似值定义为:s 的所有连续子串中与 tt 近似匹配的个数。相似值越高,说明秘钥 s 越不安全。对于不安全秘钥集合 T 中的每个秘钥 t,你需要输出它和秘钥 s 的相似值,用来对用户秘钥的安全性进行分析。

输入格式

第一行包含一个正整数 nn,表示 ss 串的长度。

第二行包含 n 个正整数 s1,s2,...,sn(1≤sin),表示 s 串。

接下来一行包含一个正整数 m,表示询问的个数。

接下来 m 个部分:

每个部分第一行包含一个正整数 k(1≤kn),表示每个 t 串的长度。

每个部分第二行包含 k个正整数 t1,t2,...,tk(1≤tin),表示 T 中的一个串 t

输入数据保证 T 中所有串长度之和不超过 200000

对于简单版本: 1≤n,m≤100

对于中等版本: 1≤n≤50000,1≤m≤500

对于困难版本: 1≤n≤50000,1≤m≤100000

输出格式

输出 mm 行,每行一个整数,即与 TT 中每个串 tt 近似匹配的 ss 的子串数量。

样例输入

5

2 3 1 3 2

3

4

3 2 1 3

2

1 3

2

3 2

样例输出

2

2

2

推荐代码 查看1943 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$87 $ms] 淡意的温柔 589810 2020-06-01 15:31:15
内存最少[$5448 $KB] 时涛涛@计算机科学与技术162 103532 2017-06-08 22:22:56
第一AC 时涛涛@计算机科学与技术162 103532 2017-06-08 22:22:56
第一挑战 AOJ大管家 103513 2017-06-08 21:34:08

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1092 挑战算法-字符串1 2017-06-08 17:00:00 请登录