首页 > 试题广场 >

E、Charmander

[编程题]E、Charmander
  • 热度指数：6 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
Charmander has a magical string s whose length is n.

At each second, every character in string s expands simultaneously, where character i will become the string Si. That means if the string contains 3 characters c1, c2 and c3, in next second the string will become .

But at any moment, each character that appears in string s can only be one of the m characters numbered from 1 to m.

Given a target string t, Charmander wants to know in which second it first appears as a substring of string s, or if it never appears?

输入描述:
The input starts with one line containing exactly one integer T, which is the number of test cases.

For each test case, the first line contains three integers n, m and k, indicating the length of string s in second 0, the size of character set and the length of string t.

Then followed by one line, consisting of n integers, indicating the string s in second 0.

Then followed by m lines, each consists of ki, Si[1], , Si[ki], representing the string Si.

Then followed by one line, consisting of k integers, indicating the string t.

- 1 ≤ T ≤ 10.
- 1 ≤ n,m,k ≤ 1000.
- .
- 1 ≤ s[i], Si[j], t[i] ≤ m.
- ki ≥ 2.


输出描述:
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and string t first appears in second y.

If string t never appears, y is supposed to be -1.
示例1

输入

2
3 2 4
2 2 2
4 1 2 2 1
5 1 1 2 1 2
1 1 2 1
3 5 1
4 4 3
3 5 4 2
2 1 1
3 4 5 3
2 2 3
3 1 5 4
1

输出

Case #1: 1
Case #2: 2
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

kmp与扩展kmp 动态规划
难度：
0条回答 951浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号