Теоретический материал
Приступим к реализации.
type
PEl = ^TEl;
TEl = record // Тип для вершины
f : boolean;
Link : array ['a' .. 'z'] of PEl;
end;
В олимпиадном программировании не рекомендуется использовать динамические переменные, так как операция new довольно долго выполняется. Поэтому заведем массив и счетчик использованных элементов.
При желании можно модифицировать реализацию с использованием динамических переменных и, таким образом, освобождать память после удаления строки. Для эффективной реализации вышеизложенного можно завести в каждой вершине счетчик количества элементов множества в поддереве, но в олимпиадах это практически не используется, поэтому останавливаться на этих модификациях не будем.
var
bor : array [0 .. maxEl] of TEl;
uk : integer; root : PEl;
procedure Init;
begin
fillchar(bor, sizeof(bor), 0);
uk := 0; root := @bor[0];
end;
procedure Insert(const s : string);
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
inc(uk);
cur^.Link[s[i]] := @bor[uk];
end;
cur := cur^.Link[s[i]];
end;
cur^.f := true;
end;
procedure Delete(const s : string);
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
Writeln('No such string');
exit;
end;
cur := cur^.Link[s[i]];
end;
cur^.f := false;
end;
function Search(const s : string) : boolean;
var
cur : PEl;
i : integer;
begin
cur := root;
for i := 1 to length(s) do begin
if cur^.Link[s[i]] = nil then begin
result := false;
exit;
end;
cur := cur^.Link[s[i]];
end;
result := cur^.f;
end;