Problem1054--「一本通 2.3 练习 2」L 语言

1054: 「一本通 2.3 练习 2」L 语言

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:HNOI 2004

标点符号的出现晚于文字的出现,所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 TTT 是由若干小写字母构成。一个单词 WWW 也是由若干小写字母构成。一个字典 DDD 是若干个单词的集合。 我们称一段文章 TTT 在某个字典 DDD 下是可以被理解的,是指如果文章 TTT 可以被分成若干部分,且每一个部分都是字典 DDD 中的单词。

例如字典 DDD 中包括单词is,your,what,name,则文章whatisyourname是在字典 DDD 下可以被理解的,因为它可以分成 4 个单词:what,is,your,name,且每个单词都属于字典 D,而文章whatisyouname在字典 DDD 下不能被理解,但可以在字典 D’=D+D’=D+D=D+you下被理解。这段文章的一个前缀whatis,也可以在字典 D 下被理解 而且是在字典 DDD 下能够被理解的最长的前缀。

给定一个字典 DDD ,你的程序需要判断若干段文章在字典 DDD 下是否能够被理解。 并给出其在字典 DDD 下能够被理解的最长前缀的位置。


Input

输入文件第一行是两个正整数 nnnmmm,表示字典 DDD 中有 nnn 个单词,且有 mmm 段文章需要被处理。

之后的 nnn 行每行描述一个单词,再之后的 mmm 行每行描述一段文章。


Output

对于输入的每一段文章,你需要输出这段文章在字典 DDD 可以被理解的最长前缀的位置。


Sample Input

4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Sample Output

14
6
0

HINT

对于 100%100\%100% 的数据,1≤n,m≤201\le n, m\le 201n,m20,每个单词长度不超过 101010,每段文章长度不超过 111 MB。


Source/Category


Submit Status