1212: [HNOI2004]L语言
1212: [HNOI2004]L语言
1212: [HNOI2004]L语言
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 643 Solved: 252
Description
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。 一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。 我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。 例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的 因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’ 在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解 而且是在字典D下能够被理解的最长的前缀。 给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。 并给出其在字典D下能够被理解的最长前缀的位置。
Input
输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。 之后的n行每行描述一个单词，再之后的m行每行描述一段文章。 其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。
Output
对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。
Sample Input
4 3 is name what your whatisyourname whatisyouname whaisyourname
Sample Output
14 6 0 整段文章’whatisyourname’都能被理解 前缀’whatis’能够被理解 没有任何前缀能够被理解
HINT
Source
题解：我真心不明白这道题为啥会被上一个DP的标签。。。觉得好晕。。。
说思路——先是根据字典建立AC自动机，然后用这个跑啊跑，跑啊跑。。。用一个数组记录下长度为N的前缀是否可以被接受，然后跑啊跑，跑啊跑，别的没了。。。几乎是AC自动机裸题啊（HansBug：居然比phile快了耶，我2352ms，你可是3000+ms哦么么哒 phile：呵呵呵好吧我也是醉了）
1 type
2 point=^node;
3 node=record
4 st:ansistring;
5 ex:longint;
6 jump,fat:point;
7 next:array['A'..'Z'] of point;
8 end;
9 var
10 i,j,k,l,m,n:longint;
11 head,p1,p2:point;
12 s1:ansistring;
13 a:array[0..2000000] of longint;
14 function getpoint:point;
15 var p1:point;c1:char;
16 begin
17 new(p1);
18 p1^.ex:=0;
19 p1^.st:='';
20 p1^.fat:=nil;
21 p1^.jump:=head;
22 for c1:='A' to 'Z' do p1^.next[c1]:=nil;
23 getpoint:=p1;
24 end;
25 procedure ins(s1:ansistring);
26 var
27 s2:ansistring;
28 i,j,k,l:longint;
29 p1,p2:point;
30 begin
31 p1:=head;s2:='';
32 for i:=1 to length(s1) do
33 begin
34 s2:=s2+s1[i];
35 if p1^.next[s1[i]]=nil then
36 begin
37 p2:=getpoint;
38 p2^.st:=s2;
39 p2^.fat:=p1;
40 p1^.next[s1[i]]:=p2;;
41 end;
42 p1:=p1^.next[s1[i]];
43 if i=length(s1) then p1^.ex:=1;
44 end;
45 end;
46 procedure linkit;
47 var
48 i,j,k,l,f,r:longint;
49 p1,p2:point; c1:char;
50 d:array[0..10000] of point;
51 begin
52 f:=1;r:=2;
53 d[1]:=head;
54 while f<r do
55 begin
56 for c1:='A' to 'Z' do
57 begin
58 if d[f]^.next[c1]<>nil then
59 begin
60 d[r]:=d[f]^.next[c1];
61 if (d[f]<>head) then
62 begin
63 p2:=d[f]^.jump;
64 while (p2^.next[c1]=nil) and (p2<>head) do p2:=p2^.jump;
65 if p2^.next[c1]<>nil then d[r]^.jump:=p2^.next[c1];
66 end;
67 inc(r);
68 end;
69 end;
70 inc(f);
71 end;
72 end;
73 function cal(s1:ansistring):longint;
74 var
75 i,j,k,l:longint;
76 p1,p2:point;
77 begin
78 p1:=head;l:=0;
79 fillchar(a,sizeof(a),0);
80 a[0]:=1;
81 for i:=1 to length(s1) do
82 begin
83 if p1^.next[s1[i]]=nil then
84 begin
85 while (p1^.next[s1[i]]=nil) and (p1<>head) do p1:=p1^.jump;
86 if p1^.next[s1[i]]<>nil then p1:=p1^.next[s1[i]]
87 end
88 else p1:=p1^.next[s1[i]];
89 p2:=p1;
90 while p2<>head do
91 begin
92 if (p2^.ex=1) and (a[i-length(p2^.st)]=1) then
93 begin
94 a[i]:=1;
95 l:=i;break;
96 end;
97 p2:=p2^.jump;
98 end;
99 end;
100 exit(l);
101 end;
102
103 begin
104 readln(n,m);head:=getpoint;
105 head^.jump:=head;
106 for i:=1 to n do
107 begin
108 readln(s1);
109 ins(upcase(s1));
110 end;
111 linkit;
112 for i:=1 to m do
113 begin
114 readln(s1);
115 writeln(cal(upcase(s1)));
116 end;
117 readln;
118 end.
119