|
||||||||||
在 A 里面找有 C 的 BTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 2398 Accepted Submission(s): 480 Problem Description 小 T 最近上班碰到了一个问题,怎么样才能用 Vscode 快速的**在 A 里面找有 C 的 B**。 他想要在代码库的一个文件 $A$ 中,找到有哪些在 $A$ 中使用到的函数 $B$ 间接地调用了小 T 所指定的语句 $C$。由于小 T 的需求比较简单,所以这里不考虑间接调用的函数中的调用关系,只需要看 $B$ 的声明中 $B'$ 是否包含 $C$ 即可。 手动处理这个问题还是有相当大的重复工作量的,但是你是一个经验丰富的**SQL BOY/GIRL**,你对小 T 说:"闹麻了,这不就是把 A 里面包含的 B,和包含 C 的 B JOIN 一下就行了吗。" 虽然是的,但是这两张表哪来呢? 为了圆你吹下的牛,现在你需要手写一个字符串解析器,用来**在 A 里面找有 C 的 B**。 接下来我们会给定一个长字符串 $A$,一个短字符串 $C$,以及 $n$ 个短字符串 $\{B_n\}$,以及其声明 $\{B'_n\}$。 我们定义一个字符串 $S$ 在字符串 $T$ 中当且仅当存在一个 $T$ 的子串 $p$ 满足:$S=p$。 Input 第一行输入一个正整数 $T$ ($1\le T\le 10$),表示总共有 $T$ 组数据。 对于每一组测试数据,首先是一个正整数 $n$ ($1\le n \le 10^5$)。 接下来是两个由小写字母构成的字符串 $A$,$C$ ($1\le |A| \le 10^5$,$1\le |C| \le 10^4$) 接下来 $n$ 行,每行读入两个由小写字母构成的字符串 $B_i$,$B'_i$ ($1\le |B_i|\le 10^4,1\le |B_i'|\le 10^5$) 每组数据中有额外限制如下:$\sum |B_i| \le 10^5,\sum |B_i'|\le 5\times 10^5$ Output 对于每一组测试数据,输出一行整数 $i$ 满足 $B_i$ 在 $A$ 中,同时 $B'_i$ 中包含 $C$,相邻的整数之间用空格分割,**注意行末不保留空格**。 假如答案集合为空,则输出一个空行。 Sample Input
Sample Output
Source | ||||||||||
|