首页 > 代码库 > tyvj1161聚会的名单（trie树）

tyvj1161聚会的名单（trie树）

2024-07-07 02:59:31   224人阅读

背景 Background
明天就是candy的生日，candy又会邀请自己的一大堆好友来聚会了！哎！又要累坏飘飘乎居士了！！
描述 Description
    明天就是candy的生日。晚上，candy找到了飘飘乎居士。她给了飘飘乎居士一张名单，名单上记录了n个candy的好朋友。可是，飘飘乎居士发现，名单上有好多重复的名字啊，这可急坏了飘飘乎居士。所幸，飘飘乎居士找到了自己的oi朋友，希望能够帮助自己。飘飘乎居士会问某个名字，而你要做的任务就是计算出名单中出现了几次该名字。
题解：
 trie模板题，贴一下网上抄来的模板……
type node=record
     got:longint;
     next:array[‘a‘..‘z‘] of longint;
     end;
var t:array[0..1000000] of node;
    s:string;
    n,m,i,tot:longint;
procedure getintree(s:string);
 var i,now:longint;
 begin
  now:=1;
  for i:=1 to length(s) do
   if t[now].next[s[i]]<>0 then now:=t[now].next[s[i]]
   else begin
         inc(tot);
         t[tot].got:=0;
         fillchar(t[tot].next,sizeof(t[tot].next),0);
         t[now].next[s[i]]:=tot;
         now:=tot;
        end;
  inc(t[now].got);
 end;
function check(s:string):longint;
 var i,now:longint;
 begin
  now:=1;
  for i:=1 to length(s) do
    if t[now].next[s[i]]<>0 then now:=t[now].next[s[i]] else exit(0);
  exit(t[now].got);
 end;
begin
 tot:=1;
 t[1].got:=0;
 fillchar(t[1].next,sizeof(t[1].next),0);
 readln(n);
 for i:=1 to n do
  begin
   readln(s);
   getintree(s);
  end;
 readln(m);
 for i:=1 to m do
  begin
   readln(s);
   writeln(check(s));
  end;
end.

 


联系
我们