首页 > 代码库 > 1212: [HNOI2004]L语言

1212: [HNOI2004]L语言

1212: [HNOI2004]L语言

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 643  Solved: 252
[Submit][Status]

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 字符串

 

题解:我真心不明白这道题为啥会被上一个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 begin104      readln(n,m);head:=getpoint;105      head^.jump:=head;106      for i:=1 to n do107          begin108               readln(s1);109               ins(upcase(s1));110          end;111      linkit;112      for i:=1 to m do113          begin114               readln(s1);115               writeln(cal(upcase(s1)));116          end;117      readln;118 end.119            

 

1212: [HNOI2004]L语言