「BZOJ1212」[HNOI2004]L语言

Description

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

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

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

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

Input

输入文件第一行是两个正整数nnmm,表示字典DD中有nn个单词,且有mm段文章需要被处理。之后的nn行每行描述一个单词,再之后的mm行每行描述一段文章。

其中1n,m201\leq n, m\leq 20,每个单词长度不超过1010,每段文章长度不超过1M1M

Output

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

Sample Input

1
2
3
4
5
6
7
8
4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Sample Output

1
2
3
14
6
0

Solution

trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

int n, m;
char s[1060900];
int ch[1060900][26], tot;
bool vis[1060900];
void ins() {
int p = 0, len = strlen(s + 1);
for(int i = 1; i <= len; ++i) {
int to = s[i] - 'a';
if(!ch[p][to]) ch[p][to] = ++tot;
p = ch[p][to];
}
vis[p] = 1;
}
bool f[1060900];
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
ins();
}
for(int i = 1; i <= m; ++i) {
scanf("%s", s + 1);
int len = strlen(s + 1);
for(int j = 1; j <= len; ++j) f[j] = 0;
f[0] = 1;
int ans = 0;
for(int j = 0; j <= len; ++j) if(f[j]) {
ans = j;
int p = 0;
for(int k = j + 1; k <= len; ++k) {
p = ch[p][s[k] - 'a'];
if(!p) break;
if(vis[p])f[k] = 1;
}
}
writeln(ans);
}
return 0;
}