2232: 单词默写-训练套题T6T1
Description
1. 单词默写 (engzam.pas/c/cpp)
【问题描述】
小D前一段日子刚刚参加了一次非常苛刻的英语考试。
考试不仅包括了听力、选择、填空等基本题型，还包括了一种特殊的单词默写题。这类题目都是按照以下形式给出的：
在本学期你所学的所有前缀是B的单词中，在课本中出现次数不少于L的有多少个。
例如小D这个学期只学过三个单词a、ab、bc，它们出现的次数分别是1、2、3；若给出询问（B = a，L = 2），那么前缀为a的单词一共有两个，是a和ab，其中频率不少于2的只有一个，是ab。
这个学期小 D学过的单词非常多，而考试给出的这类询问也非常多。这么困难的任务小D当然不可能解决，于是这个问题被交给了你。
【输入】
输入文件第一行包含两个用空格隔开的整数N、M，分别表示小D本学期学过的单词数和考试中出现的询问数。
接下来N行，每行包含用空格隔开的一个单词A和一个整数P，描述小D本学期学过的一个单词A以及其出现的次数P。
接下来M行，每行包含用空格隔开的一个单词B和一个整数L，描述考试中给出的一个询问。
你可以假定所有单词均由小写字母组成，且长度不超过10。
【输出】
输出文件一共包含M行。
对于每个考试的询问输出一行一个整数，表示该问题的答案。
【输入输出样例】
|
engzam.in
|
engzam.out
|
|
3 3
a 1
ab 2
bc 3
a 2
a 1
a 3
|
1
2
0
|
【输入输出样例说明】
前缀为a的单词一共有两个，是a和ab，出现次数分别为1和2。
【数据规模】
对于50%的测试数据，满足N、M ≤ 1 000
对于100%的测试数据，满足N、M ≤ 100 000，P、L ≤ 100 000
HINT
Trie树（pascal版）
Trie树就是字符树，其核心思想就是空间换时间。
举个简单的例子。
给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，第一次出现第几个位置。
这题当然可以用hash来，但是我要介绍的是trie树。在某些方面它的用途更大。比如说对于某一个单词，我要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。
现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了……
假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树就是这样的。
那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
这样一来我们询问和插入可以一起完成，所用时间仅仅为单词长度，在这一个样例，便是10。
我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。
程序非常好实现，区区几行，我就不写了，自己琢磨吧。
如果还是不懂请留言。
下面提供一个查找单词是否在给定的字典中的标程：
program trie;
type
rec=record
Got:boolean;
next:array['a'..'z'] of Longint;
end;
var
n,i,j,Now,Tn:Longint;
s:string;
T:array[1..1000] of rec;
flag:boolean;
begin
Readln(n);
Tn:=1;
T[1].Got:=False;
fillchar(T[1].next,sizeof(T[1].next),0);
for i:=1 to n do
begin
readln(s);
Now:=1;
for j:=1 to length(s) do
if T[now].Next[s[j]]<>0 then now:=t[now].next[s[j]] else
begin
Inc(Tn);
T[tn].Got:=false;
fillchar(T[tn].next,sizeof(T[tn].next),0);
T[Now].next[s[j]]:=Tn;
Now:=Tn;
end;
T[now].Got:=true;
end;
readln(s);
while s<>'exit' do
begin
Now:=1;flag:=true;
for j:=1 to length(s) do
if T[now].Next[s[j]]<>0 then now:=t[now].next[s[j]] else
begin
flag:=false;
break;
end;
if flag then
if T[now].Got=false then flag:=false;
if flag then writeln('the word is in the tree') else
writeln('can''t find it!');
Readln(s);
end;
end.
一个单词前缀树的题，但是我却用trie树+bm算法简化版做的
密码破译
【问题描述】
由于最近功课过于繁忙，Tim竟然忘记了自己电脑的密码，幸运的是Tim在设计电脑密码的时候，用了一个非常特殊的方法记录下了密码。这个方法是：Tim把密码和其它的一些假密码共同记录在了一个本子上面。为了能够从这些字符串中找出正确的密码，Tim又在另外一个本子上面写了一个很长的字符串，而正确的密码就是在这个字符串中出现次数最多的一个密码。例如串ababa，假若密码是abab和aba，那么正确的密码是aba，因为aba在这个字符串中出现了2次。
现在你得到了Tim的这两个本子，希望你能够编写一个程序帮助Tim找出正确的密码。
【输入】
输入由两个部分组成。其中第一部分由若干行组成，每一行记录了一个密码，密码的均长度小于等于255位，并且都由小写字母组成。然后一个空行，第二部分记录了一个很长的字符串，并且以’.’结束，其中只包含了小写字母。
【输出】
输出文件名为Pass.out。输出文件由仅有一行，为一个整数，表示正确密码在字符串中出现的次数。如果这个出现次数为0，输出“No find”。
【样例】：
Pass.in Pass.out
ab 6
abc
bdc
abcd
abcabcabcdbdabcbabdbcabdbdbdbd.
program pass;
const
filein='pass.in';
fileout='pass.out';
type
rec=record
which:Longint;
Next:array['a'..'z'] of Longint;
end;
var
o,now,i,Tn,Dn,temp,Ans:Longint;
s:string;
c:char;
T:array[1..1000000] of REc;
data:array[1..5000] of string;
dLong:array[1..5000] of longint;
use:array[1..5000] of boolean;
d:array[1..3000000] of char;
Appear:array['a'..'z'] of Longint;
Long:Longint;
f:boolean;
function Compare(x:Longint):Longint;
var
s,i,Now,L,temp:Longint;
begin
s:=0;
fillchar(appear,sizeof(appear),0);
L:=length(data[x]);
for i:=1 to L do
Appear[data[x]]:=i;
Now:=L;
while NOw<=Long do
begin
if D[now]<>data[x][L] then Inc(now,L-Appear[D[now]]) else
begin
temp:=L-1;
while (temp>0) and (Data[x][temp]=d[Now-(L-temp)]) do dec(temp);
if temp=0 then Inc(s);
Inc(Now);
end;
end;
Compare:=S;
end;
procedure sort(l,r:Longint);
var
i,j,x:Longint;
sy:string;
ly:Longint;
begin
i:=l;j:=r;x:=dLong[(l+r) div 2];
repeat
while dLong<x do inc(i);
while dlong[j]>x do dec(j);
if i<=j then
begin
sy:=data;
data:=data[j];
data[j]:=sy;
ly:=dlong;
dlong:=dlong[j];
dlong[j]:=ly;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
begin
fillchar(use,sizeof(use),true);
fillchar(t,sizeof(t),0);
Assign(input,filein);
Assign(output,fileout);
rewrite(output);
reset(input);
tn:=1;
readln(s);
Dn:=0;
while s<>'' do
begin
Inc(dn);
data[dn]:=s;
dLong[dn]:=length(s);
readln(s);
end;
sort(1,Dn);
for o:=1 to Dn do
begin
s:=data[o];
NOw:=1;
f:=true;
for i:=1 to Length(s) do
if t[now].Next[s]<>0 then
begin
Now:=t[now].next[s];
if t[now].which<>0 then
begin
f:=false;
break
end;
end else
begin
Inc(tn);
t[now].next[s]:=tn;
now:=tn;
end;
if f then t[now].which:=o;
if not f then use[o]:=false;
end;
Long:=0;
repeat
read(c);
if c<>'.' then
begin
Inc(Long);
d[Long]:=c;
end;
until c='.';
for i:=1 to Dn do
begin
if use then
begin
temp:=Compare(i);
if temp>ans then ans:=temp;
end;
end;
if ans=0 then writeln('No find') else
writeln(Ans);
close(input);
close(output);
end.