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 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            

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

22640
来自专栏Petrichor的专栏

python: 装饰器 / 迭代器 / 生成器

写在 被装饰函数 的 正上方 。可提前注明接下来的介绍内容,例如@property、@classmethod、@staticmethod。

19320
来自专栏java工会

java冒泡排序和快速排序

41230
来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

33770
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

37240
来自专栏一枝花算不算浪漫

HashMap中的hash算法总结

算法一直是我的弱项,然而面试中基本是必考的项目,刚好上次看到一个HashMap的面试题,今天也来学习下 HashMap中的hash算法是如何实现的。

61120
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

11920
来自专栏数据结构与算法

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

49140
来自专栏小樱的经验随笔

洛谷 P1019 单词接龙【经典DFS,温习搜索】

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”...

40760
来自专栏赵俊的Java专栏

奇偶分割数组

20240

扫码关注云+社区

领取腾讯云代金券