INFOMAN брой 6
{ This is the input data: A; B; N; Sequence_of_0_and_1; 2 :
2
4
10
010100100100010001111011000010100110011110000100100111100100000002
НАМИРАНЕ НА НАЙ-ЧЕСТО СРЕЩАНИ ПОДНИЗОВЕ
---------------------------------------
(Задачата е от 10-тата международна олимпиада по информатика - I ден)
Дадени са числата A, B, N (A<=B<12,N<=20) и редица от знаци 0 и 1, завър-
шваща с 2. Да се намерят всички битови низове с дължина между A и B, които
се срещат най-често във файла с данни. Честота на битов низ наричаме броя
срещания на този низ във файла с данни. Битовите низове могат да се припок-
риват и се търсят низове, които се срещат поне веднъж. В изходния файл тря-
бва да се отпечатат най-много N реда - списък от N-те най-големи честоти и
съответните им низове. Ако няколко низа имат една и съща честота,те трябва
да се извеждат в намаляващ ред спрямо дължината си,а когато са с равни дъл-
жини в обратен лексикографски ред. Размерът на входния файл не надвишава 2
мегабайта.
За да решим задачата, първо ще помислим какъв алгоритъм трябва да прило-
жим. Понеже входния файл е до 2 MB, трябва алгоритъма да е с линейна слож-
ност спрямо дължината на редицата от 0 и 1,която анализираме. Понеже A и B
са ограничени до 12, можем да си направим табличка c[i,j],в която за всеки
подниз в дължина i и стойност j пазим колко пъти се е срещал. Вместо да па-
зим низовете, понеже те са битови,можем да пазим тяхната стойност като дво-
ични числа. Така спестяваме много памет. Първоначално нулираме табличката
c[]. Сканираме дадения входен битов низ като образуваме поднизовете с дъл-
жини от A до B,които могат да се получат от него. Нека val[i] е стойността
на низа, имащ дължина i символа и завършва в текущия символ. Ясно е, че то-
зи низ е подниз на дадената за анализ редица. Нека вземем следващия символ
от дадената редица и го добавим отдясно на низа, val[i] и премахнем най-ле-
вия символ на val[i]. Получаваме позниз, който има дължина i символа и за-
вършва в текущия символ. Ето как можем да получаваме чрез линейна сложност
спрямо дадената редица всички нейни поднизове с дължина i. На всеки ход са-
мо премахваме най-левия символ от текущия подниз и добавяме следващия сим-
вол от редицата. Като стигнем края на редицата, значи сме намерили всичите
поднизове с дължина i, които се част от дадената редица. По този начин мо-
жем и да ги преброим. Като получим някой подниз с дължина i и стойност val
можем да увеличим броя на срещанията на този низ - c[i,val].Понеже работим
не с низовете,а с техните битови стоности, изтриването на най-левия символ
и прибавянето на текущия най-вдясно се извършва чрез битови операции: логи-
ческо "или" с новия символ и логическо "и" с (2^i-1). Понеже търсим всички
най-дълги поднизове не само с дължина i, но с дължина от A до B, прилагаме
същата операция за i=A..B. По този начин преброяваме всички низове с дължи-
на от A до B. Отпечатването става така: Намираме максималната честота на
низ (максималното c[A..B,....]). След това отпечатваме тази честота и чрез
претърсване на c намираме и отпечатваме всички низове, които имат тази чес-
тота. Обхождането правим с намаляваща дължина в обратен лексикографски ред,
като след като отпечатаме даден низ му нулираме честотата. Повтаряме това
N пъти или докато не получим 0 за максимална честота.
}
CONST InFileName = 'contact.pas';
OutFileName = '';
MaxAB = 12;
BitMask: array[1..MaxAB] of longint =
(1,3,7,15,31,63,127,255,511,1023,2047,4095);
TYPE TCount = array[0..1 shl MaxAB-1] of longint;
VAR A,B,N: integer;
c: array[1..MaxAB] of ^TCount;
Procedure WriteOutput; {Отпечатва максималните честоти и съответните низове}
Var OutF: Text;
Count: longint;
Procedure FindMaximalCount;
Var i,j:integer;
Begin
Count:=0;
for i:= a to b do
for j:= 0 to BitMask[i] do
if c[i]^[j] > Count then
Count:= c[i]^[j];
End;
Procedure WriteToFileAllCount;
Function GetValue(len:integer;val:longint): string;
Var s: string; {Връща битовия низ,който има стойност val и дължина len}
i: integer;
Begin
s:= '';
for i:= 1 to len do
begin
s:= chr(val mod 2 + ord('0')) + s;
val:= val div 2;
end;
GetValue:= s;
End;
Var i,j: integer;
Begin
for i:= b downto a do
for j:= BitMask[i] downto 0 do
if c[i]^[j] = Count then
begin
c[i]^[j]:= 0;
Write(OutF,' ',GetValue(i,j));
end;
End;
Begin
Assign(OutF,OutFileName); Rewrite(OutF); WriteLn(OutF);
for N:= 1 to N do
begin{N пъти намира максималната честота и отпечатва всички низове с нея}
FindMaximalCount;
if Count = 0 then break;
Write(OutF,Count);
WriteToFileAllCount;
WriteLn(OutF);
end;
Close(OutF);
End;
Procedure Solve; {Намира в c[] колко пъти се среща всеки битов низ}
Var i,value: integer;
info: array[1..MaxAB] of
record len:integer; val:longint; end;
F: Text;
ch: char;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,A); ReadLn(F,B); ReadLn(F,N);
for i:= A to B do
begin
GetMem(c[i], (1 shl i)*sizeof(longint));
FillChar(c[i]^, (1 shl i)*sizeof(longint), 0);
end;
FillChar(info,SizeOf(info),0);
repeat
Read(f,ch); if ch = '2' then Break;
value:= ord(ch) - ord('0');
for i:= A to B do
with info[i] do
begin
if len < i then inc(len);
val:= (val shl 1) + value;
val:= val and BitMask[i];
if len = i then inc(c[i]^[val]);
end;
until false;
Close(F);
End;
BEGIN
Solve;
WriteOutput;
END.