#P2292. [HNOI2004] L 语言

    ID: 1304 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2004各省省选湖南O2优化状态压缩状压AC 自动机

[HNOI2004] L 语言

题目描述

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

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

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

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

输入格式

第一行两个整数 nnmm,表示字典 DD 中有 nn 个单词,且有 mm 段文章需要被处理。

接下来 nn 行,每行一个字符串 ss,表示字典 DD 中的一个单词。

接下来 mm 行,每行一个字符串 tt,表示一篇文章。

输出格式

对于输入的每一篇文章,你需要输出一行一个整数,表示这段文章在字典 DD 可以被理解的最长前缀的位置。

4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

14
6
0

提示

样例 1 解释

  • 对于第一个询问,整段文章 whatisyourname 都能被理解。
  • 对于第二个询问,前缀 whatis 能够被理解。
  • 对于第三个询问,没有任何前缀能够被理解。

数据规模与约定

  • 对于 80%80\% 的数据,保证 m20m \leq 20t106|t| \leq 10^6
  • 对于 100%100\% 的数据,保证 1n201 \leq n \leq 201m501 \leq m \leq 501s201 \leq |s| \leq 201t2×1061 \leq |t| \leq 2 \times 10^6sstt 中均只含小写英文字母。

提示

  • 请注意数据读入对程序效率造成的影响。
  • 请注意【数据规模与约定】中标注的串长是单串长度,并不是字符串长度和。

说明

本题数据有加强,其中前 80%80\% 的数据为原测试数据。