# 1212: [HNOI2004]L语言

## 1212: [HNOI2004]L语言

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 643  Solved: 252

[Submit][Status]

## Sample Input

4 3 is name what your whatisyourname whatisyouname whaisyourname

## Sample Output

14 6 0 整段文章’whatisyourname’都能被理解 前缀’whatis’能够被理解 没有任何前缀能够被理解

## Source

Dp 字符串

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;
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;
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
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;
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;
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
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
106      for i:=1 to n do
107          begin
109               ins(upcase(s1));
110          end;
112      for i:=1 to m do
113          begin
115               writeln(cal(upcase(s1)));
116          end;
118 end.
119

251 篇文章37 人订阅

0 条评论

## 相关文章

22640

19320

41230

33770

37240

61120

11920

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

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

49140

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

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

40760

20240