USACO 2.3.1 Prefix

题目解答

这个程序是有史以来我编得最认真的usaco题目,虽然这个程序很慢,甚至在主程序部分使用了一点歪招?!但是这是使用递归思想的,非指针的Trie!没有优化,所以在贴上这个程序后,再贴一个正规一点的。

运行结果

Compiling…
Compile: OK Executing…
Test 1: TEST OK [0.000 secs, 6792 KB]
Test 2: TEST OK [0.000 secs, 6796 KB]
Test 3: TEST OK [0.000 secs, 6828 KB]
Test 4: TEST OK [0.000 secs, 6824 KB]
Test 5: TEST OK [0.032 secs, 6828 KB]
Test 6: TEST OK [0.670 secs, 6828 KB]
All tests OK.

程序

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
program prefix;
type node=record
data:char;
son:integer;
jl:boolean;
er:array[1..1800]of integer;
end;
var ji,total,root,max,k:longint;
zd:array[1..1800]of node;
y1:array[1..200]of string;
ls:array[1..200000]of boolean;
s:ansistring;
flag:boolean;
procedure find(x:string;wz,c:integer);
var i:integer;
begin
for i:=1 to zd[wz].son do
begin
if zd[zd[wz].er[i]].data=x[c] then
begin
if c+1<=length(x) then find(x,zd[wz].er[i],c+1)
else begin
if zd[zd[wz].er[i]].jl then flag:=true;
exit;
end;
end;
end;
end;
procedure insert(x:string;y,z:integer);
var i:integer;
f:boolean;
begin
f:=true;
if zd[y].son=0 then
begin
inc(total);
inc(zd[y].son);
zd[y].er[zd[y].son]:=total;
zd[total].data:=x[z];
if (z+1)<=length(x) then
insert(x,total,z+1)
else begin zd[total].jl:=true;exit;end;
end
else
for i:=1 to zd[y].son do
if zd[zd[y].er[i]].data=x[z] then
begin
if (z+1)<=length(x) then
begin
insert(x,zd[y].er[i],z+1);
exit;
end
else begin zd[total].jl:=true;exit;end;
end
else begin f:=false;end;
if not f then
begin
inc(total);
inc(zd[y].son);
zd[y].er[zd[y].son]:=total;
zd[total].data:=x[z];
if (z+1)<=length(x) then
insert(x,total,z+1)
else begin zd[total].jl:=true;exit;end;
end;
end;
procedure init;
var i:longint;
te:char;
temp:ansistring;
begin
root:=1;
zd[root].data:=' ';
zd[root].son:=0;
total:=1;
ji:=1;
repeat
while not eoln(input) do
begin
read(te);
if te<>'.' then
if (te=' ') then
inc(ji)
else if te in ['A'..'Z'] then
y1[ji]:=y1[ji]+te;
end;
if eoln(input) then inc(ji);
readln;
until te='.';
max:=-1;
for i:=1 to ji do
begin
insert(y1[i],root,1);
if length(y1[i])>max then max:=length(y1[i]);
end;
s:='';
k:=0;
while not eof(input) do
begin
readln(temp);
k:=k+length(temp);
s:=s+temp;
end;
end;
procedure main;
var i,j,q,head,tail:longint;
st:string;
begin
if k>100000 then
begin
head:=k div 2;
tail:=k;
end
else
begin
head:=1;
tail:=k;
end;//由于怕通不过,所以这里计算了一下数学期望,大于100000的数据折半处理。当然前一半在适当情况还是要算的。记得noip2008火柴棒等式我就使用了这种思想。
for i:=head to tail do
begin
st:='';
for j:=1 to max do
begin
flag:=false;
st:=st+s[i+j-1];
find(st,root,1);
if flag then
for q:=i to i+j-1 do
ls[q]:=true;
end;
end;
for i:=head to tail do
if not ls[i] then
begin
writeln(i-1);
exit;
end;
if ls[k] then writeln(k);
end;
begin
assign(input,'prefix.in');
reset(input);
assign(output,'prefix.out');
rewrite(output);
init;
main;
close(input);
close(output);
end.

另外一种字符串匹配的做法:

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
program prefix;
const cht=['A'..'Z'];
var i,j,n,t:longint;
tmp:char;
temp,s:ansistring;
a:array[1..200]of string[10];
f:array[0..200000]of boolean;
begin
assign(input,'prefix.in');
reset(input);
assign(output,'prefix.out');
rewrite(output);
t:=1;
while tmp<>'.' do
begin
read(tmp);
if tmp in cht then
a[t]:=a[t]+tmp
else inc(t);
end;
while not eof do
begin
readln(temp);
s:=s+temp;
end;
dec(t);
n:=length(s);
f[0]:=true;
for i:=1 to n do
for j:=1 to t do
if length(a[j])<=i then
if copy(s,i-length(a[j])+1,length(a[j]))=a[j] then
if f[i-length(a[j])] then
begin
f[i]:=true;
break;
end;
for i:=n downto 0 do
if f[i] then
begin
writeln(i);
halt;
end;
close(input);
close(output);
end.

后记

本文是原新浪博客的移植,附:全部USACO题目解答