INFOMAN брой 4
{ This is the input data:
insert the
check than
insert there
insert that
insert tree
insert threw
check three
check that
stop
СХОДНИ ДУМИ
-----------
Казваме, че две думи са сходни ако от едната от тях може да се получи дру-
гата чрез едно от следните действия:
a) изтриване на произволна буква
b) размяна на две последователни букви
c) замяна на произволна буква с друга
Даден е входен файл, който съдържа на всеки ред по един операторите:
insert <word>
check <word>
stop
Операторът insert вмъква в речника думата <word> ако я няма вече; stop прек-
ратява обработката на входния файл и спира програмата, а check проверява да-
ли посочената дума е вече в речника или ако я няма проверява дали в него ня-
ма някоя сходна дума. Ако думата я има се отпечатва дмата и 'YES'. Ако я ня-
ма и в речника няма сходни думи се отпечатва думата и 'NO', а ако в речника
думатя я няма, но там има сходни на нея думи, се отпечатва думата, 'MAY BE'
и всички сходни на нея думи.
РЕШЕНИЕ: Понеже можем да имаме до 15000 думи, ще ги съхраняваме динамично
и за всяка дума ще заемаме толкова байта памет, колкото е дълга тя + 1. Ко-
гато добавяме дума, претърсваме целия речник и ако я няма, я добавяме. Кога-
то проверяваме дума, ако я има, отпечатваме 'YES'. Ако я няма, проверяваме
за всяка дума от речника дали не е сходна на въпросната дума. Ако са намере-
ни сходни думи, те се отпечатват,а иначе се отпечатва 'NO'. Проверката дали
две думи са сходни се дели на 3 случая:
1. Ако думите имат еднакъв брой букви, се намира първата различна буква,
проверява се дали ако разменим текущата със следващата буква на дума-
та, така получените две букви ще съвпаднат и ако съвпаднат се продъл-
жава сравнението от текущата позиция+2 /случай b)/.Ако ли пък не съв-
паднат, просто прескачаме текущата буква /случай c)/. Ако до края на
сравнението до края на двете думи няма други разлики, думите са сход-
ни, а иначе не са.
2. Ако едната дума има една буква повече от другата,намираме първата не-
съвпадаща буква, прескачаме я и продължаваме сравнението.Ако до края
няма други разлики, думите са сходни, а иначе не са.
3. Ако едната дума е по-дълга от другата с два или повече символа, думи-
те не са сходни.
Алгоритъма има сложност от порядъка на брой_думи_в_файла * дължина_на_файла,
която обаче е за най-лошия случай и никога не се достига. За средния случай
сложността е много по-малка.Понеже операциите добавяне на дума преобладават
пред операциите за проверка на дума, е необходимо добавянето и търсенето на
точните думи да е бързо. Затова вместо да съхраняваме в линеен масив низове-
те в паметта, можем да ги държим в двоично дърво и така когато търсим дали
една дума вече я няма,сложността няма да е N (до 15000*дължина_на_файла), а
logN (до 14*дължина_на_файла). Това е съществено ускорение при много голям
брой думи и малко операции за проверка или при операции за проверка, които
намират точната дума в речника. Реализацията на това двоично и при това ба-
лансирано дърво е реализирана в модула Objects на Turbo Pascal. Обектът се
казва TSortedCollection и на практика е сортиран списък от указатели, броя
на които не е фиксиран и може да се променя динамично. При добавяне на еле-
мент обектът автоматично прави двоично търсене за да провери дали елементът
вече го няма и ако го няма го добавя с константна сложност.
}
USES Objects;
TYPE TBinaryStringTree = object(TSortedCollection)
function Compare(Key1,Key2:pointer): integer; virtual;
end;
Function TBinaryStringTree.Compare(Key1,Key2:pointer): integer;
Begin
if string(Key1^) = string(Key2^) then Compare:= 0
else if string(Key1^) > string(Key2^) then Compare:= 1
else Compare:= -1;
End;
CONST InFileName = 'input2.6';
VAR W: TBinaryStringTree;
F: Text;
S: string;
Function FindExact(const S: string): boolean;
Var i: integer;
Begin
FindExact:= W.Search(@S,i);
End;
Procedure DoInsert(const S:string);
Var NewS: Pstring;
Begin
GetMem(NewS,length(S)+1); NewS^:=S;
W.Insert(NewS);
End;
Function Similar(const S1,S2:string): boolean;
Var L1,L2,Poz: integer;
Begin
L1:=length(S1); L2:=length(S2);
if L1 = L2 then
begin
Poz:=1;
while (Poz <= L1) and (S1[Poz] = S2[Poz]) do
Inc(Poz);
if Poz < L1 then
if (S1[Poz] = S2[Poz+1]) and (S1[Poz+1] = S2[Poz]) then
Inc(Poz);
Inc(Poz);
while (Poz <= L1) and (S1[Poz] = S2[Poz]) do
Inc(Poz);
Similar:= Poz > L1;
end
else if abs(L1-L2) = 1 then
begin
Poz:=1;
while (Poz <= L1) and (S1[Poz] = S2[Poz]) do
Inc(Poz);
if L1 > L2 then
begin
while (Poz < L1) and (S1[Poz+1] = S2[Poz]) do
Inc(Poz);
Similar:= (Poz = L1);
end
else
begin
while (Poz < L2) and (S1[Poz] = S2[Poz+1]) do
Inc(Poz);
Similar:= (Poz = L2);
end;
end
else Similar:=false;
End;
Procedure DoCheck(const S:string);
Var Found: boolean;
i: integer;
Begin
if FindExact(S) then
begin WriteLn(S,' YES'); Exit; end;
Found:=false;
for i:= 0 to W.Count-1 do
if Similar(S,string(W.At(i)^)) then
begin
if not Found then
WriteLn(S,' MAY BE');
WriteLn(' ',string(W.At(i)^));
Found:=true;
end;
if not Found then
WriteLn(S,' NO');
End;
BEGIN
WriteLn;
W.Init(4092,256);
Assign(F,InFileName); Reset(F); ReadLn(F);
repeat
ReadLn(F,S);
readln(F);
if S[1] = 's' then Break;
if S[1] = 'i' then DoInsert(copy(S,8,255));
if S[1] = 'c' then DoCheck(copy(S,7,255));
until false;
Close(F);
END.