 |
 |
 |
Скачать программы Все программы автора
АБРАКАДАБРА
Во время своей работы алгоритм сжатия данных методом «сортировки блока» применяет к блокам данных преобразование, которое определяется следующим образом.
Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, т.е. если S=a1a2…aN, где ai — i–ый символ
строки S, то P=apap+1…aNa1…ap-1, где 1£p£N. Рассмотрим таблицу M размера N´N, строками которой есть все ротации строки S,
отсортированные в лексикографическом (словарном) порядке по возрастанию.
Пусть строка L есть последний столбик таблицы M. Прямое преобразование получает на вход строку S, выдает строку L и число K — номер строки таблицы M, который содержит строку S. (Если таких строк несколько, выдается номер любой из них).
Для S='abraka' таблица M изображена на рисунке. Строка S находится во второй строке таблицы M, L=‘karaab'.
Задание
Напишите программу ABRAKA, которая выполняет обратное преобразование, т.е. получает на вход строку L и число K, и выдает строку S.
Входные данные
Первая строка входного файла ABRAKA.DAT содержит два целых числа: K и N, 1£N£30000, 1£K£N. Вторая строка содержит N символов строки L — маленьких латинских букв.
Выходные данные
Единственная строка выходного файла ABRAKA.SOL должна содержать строку S.
Пример входных и выходных данных
|
ABRAKA.DAT |
ABRAKA.SOL |
|
2 6 karaab |
abraka |
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program Abraka;
type
tArray = array [0..29999] of char;
tIntArray = array [0..29999] of integer;
var
fr, fw: text;
k, n: integer;
l: tArray;
s: ^tArray;
p: ^tIntArray;
c: array ['a'..'z'] of integer;
{ c: array [char] of integer;}
procedure Main;
var
i, j, sum: integer;
ch: char;
begin
{let's fill array c with zeroes}
FillChar(c, sizeof(c), 0);
for i:=0 to n-1 do
begin
p^[i] := c[l[i]];
inc(c[l[i]]);
end;
{now c[ch] is a number of chars ch in the string l;
p[i] - is a number of chars l[i] in the string l[0..i-1]}
sum := 0;
for ch:='a' to 'z' do
begin
sum := sum + c[ch];
c[ch] := sum - c[ch];
end;
{now c[ch] is a number of chars, that are less then ch, in the string l}
i := k - 1;
for j:=n-1 downto 0 do
begin
s^[j] := l[i];
i := p^[i] + c[l[i]];
end;
end;
var
i:integer;
begin
GetMem(s, 30000);
GetMem(p, 60000);
assign(fr, 'abraka.dat');
reset(fr);
assign(fw, 'abraka.sol');
rewrite(fw);
readln(fr, k, n);
for i:=0 to n-1 do
read(fr, l[i]);
Main;
for i:=0 to n-1 do
write(fw, s^[i]);
writeln(fw);
close(fw);
close(fr);
FreeMem(p, 60000);
FreeMem(s, 30000);
end.
|
|
|
