题解 P2580 【于是他错误的点名开始了】

· · 题解

标解为字典树，水题……

裸的字典树，但是用指针实现

应该不能直接开二维数组容易挂MLE

题目说每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50），直接想到字典树

弄个指针中间的record为如下2个

type
node=^rec;
rec=record
 next:array[1..26]of node;//下一层的26字母
 vis:boolean;//有无被访问
end;

至于是否记录是否为单词结束，就无关紧要了 每次成功找到名字就把p^.vis=false(初始为true)；

如果当前层的某一个字母找不到了(p^.next[w]=nil) 那么就判定为无学生名字exit

注意在每次新建指针前先new一下，否则爆216（据说是因为访问无效内存？！）

除了指针恶心点，其他都还好

恩，接下来讲讲暴力：

快排(n log n); 二分查找(m log n);

弄点**维护一下是否找过该名字（二叉排序树）应该也能在m log n内完成；

所以暴力时间复杂度O（m log n）；

BUT，容易卡内存……

而字典树，巧妙的利用有些单词的前缀可能一样的来简化空间复杂度（特别加了指针）

时间也是比较快速O(k)查询O(k)建立【k为常数基本为O(1)】（和层数有关，由于名字长度不超过 50，所以常数k最大为50）

pascal代码如下：

const maxn=10000;
type
node=^rec;
rec=record
 next:array[1..26]of node;
 vis:boolean;
end;
var root:node;
    s:string;
    n,m,p,i:longint;
procedure insert(s:string);
var p,newnode:node;
    w,i,j:longint;
begin
 p:=root;
 for i:=1 to length(s) do begin
  w:=ord(s[i])-96;
  if  p^.next[w]=nil then begin
   new(newnode);
   for j:=1 to 26 do newnode^.next[j]:=nil;
   p^.next[w]:=newnode;
   p:=newnode;
  end else p:=p^.next[w];
 end;
 p^.vis:=true;
end;
function find(s:string):longint;
var p:node;
    i,w:longint;
begin
 p:=root;
 for i:=1 to length(s) do begin
  w:=ord(s[i])-96;
  if (p^.next[w]=nil) then exit(3);
  p:=p^.next[w];
 end;
 if p^.vis=false then exit(2)
 else begin p^.vis:=false; exit(1); end;
end;
begin
 new(root);
 for i:=1 to 26 do root^.next[i]:=nil;
 root^.vis:=false;
 readln(n);
 for i:=1 to n do begin
  readln(s);
  insert(s);
 end;
 readln(m);
 for i:=1 to m do begin
  readln(s);
  p:=find(s);
  case p of
   1:begin writeln('OK');end;
   2:begin writeln('REPEAT');end;
   3:begin writeln('WRONG');end;
  end;
 end;
end.