首页 > 代码库 > 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