首页 > 代码库 > noi4_6_1799[最短前缀]

noi4_6_1799[最短前缀]

字典树。数据不大,代码不短……

type knot=record           sum:longint;           son:array[0..30] of longint;           ch:char;          end;var tree:array[1..30000] of knot;    st:array[1..1000] of string[20];    n,tot:longint;procedure insert(k,len:longint);var i:longint;begin inc(tree[k].sum); if len>length(st[n]) then exit; for i:=1 to tree[k].son[0] do  if tree[tree[k].son[i]].ch=st[n][len] then   begin     insert(tree[k].son[i],len+1);    exit;   end; inc(tree[k].son[0]); inc(tot); tree[k].son[tree[k].son[0]]:=tot; tree[tot].sum:=0; tree[tot].ch:=st[n][len]; tree[tot].son[0]:=0; insert(tot,len+1);end;procedure find(sn,k,len:longint);var i:longint;begin if k<>1 then write(tree[k].ch); if len>length(st[sn]) then exit; if tree[k].sum=1 then   exit; for i:=1 to tree[k].son[0] do  if tree[tree[k].son[i]].ch=st[sn][len] then   find(sn,tree[k].son[i],len+1);end;procedure prepare;begin tree[1].son[0]:=0; tree[1].ch:=‘ ‘; tree[1].sum:=0;end;procedure scanf;begin n:=0; tot:=1; while not eoln do  begin   inc(n);   readln(st[n]);   insert(1,1);  end;end;procedure printf;var i:longint;begin for i:=1 to n do  begin   write(st[i],‘ ‘);   find(i,1,1);   writeln;  end;end;begin prepare; scanf; printf; end.

noi4_6_1799[最短前缀]