сокращение строки, помогите решить задачку... Опции

[Bard]

вчера нам учитель задал такую вот задачку:

вводиться строка из латинских букв требуеться ее сжать...

например:
если AABCCCCC то надо ее сжать таким образом 2AB5C
или
AAAAAAAAAABABABCCD то 10A2(BA)B2CD
Например, последовательность "ABABCABABC" можно записать как 2(2(AB)C)

помогите с алгоритмом...

Добавлено через 5 мин.
а вот и оригинал задачи:

Сжатие

Рассмотрим последовательность строк, состоящую только из больших латинских букв. Например, последовательность "AAAABBBAAAABBBC" - одна из таких последовательностей. Ее длина 15 символов. Поскольку в последовательности могут быть только буквы, можно заменить несколько подряд идущих одинаковых букв одной такой буквой, поставив перед ней натуральное число - количество повторений буквы.
Например, вышеупомянутую последовательность можно записать как "4A3B4A3BC" и длина такой записи будет только 9 символов. Легко видеть, что группа 4A3B повторяется в этой записи два раза подряд. Запишем это повторение, применяя скобки для выделения повторяющейся группы, а перед группой напишем количество ее повторений: 2(4A3B)C . Длина этой последовательности уже только 8 символов. Разумеется, могут случиться повторяющиеся группы на нескольких уровнях. Например, последовательность "ABABCABABC" можно записать как 2(2(AB)C)

Задача
Напишите программу OLI5B, которая по данной исходной последовательности находит и выводит сжатую последовательность.

Формат входных данных (файл B.IN )
В единственной строке текстового файла B.in дана исходная последовательность. Ее длина не превосходит 250 символов

Формат выходных данных (файл B.OUT )
В единственной строке текстового файла B.out следует вывести сжатую последовательность.

Например:
Тесты Входные данные - B.IN Выходные данные - B.OUT
1 AABCCCCC 2AB5C
2 EEEEEEEEEEEEEEEEEEEEEU 21EU
3 AAAAAAAAAABABABCCD 10A2(BA)B2CD

[volvo]

Если не то же самое - то ОЧЕНЬ похоже:
Задача про строки и повторяющиеся символы.

[Bard]

большое спасибо но самая главная трудность вот сдесь:

AAAAAAAAAABABABCCD = 10A2(BA)B2CD

буду очень благодарен если поможете с реализацией этого алгоритма...

[Malice]

Приведенная ссылка - очень похожая задача, но не то.. Разница именно в скобках, т.е. в когда повторяется не 1 символ, а несколько. Здесь однозначно пахнет рекурсией..

[volvo]

Bard, а можно вопрос? Почему, собственно, вариант:
AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?

Сообщение отредактировано: volvo - 10.05.2007 8:50

[samec]

Bard, а можно вопрос? Почему, собственно, вариант:
AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?

судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.

[volvo]

Интересно... Максимальное сжатие достигается как раз обратным процессом - сначала все последовательности длины Length(s) div 2, и потом по убывающей до 1...

Кстати, если скомбинировать программу по той ссылке, что я привел выше и вот по этой:
Интересная задача на рекурсию

то очень может быть, что получится решить задачу... Надо будет попробовать.

[Malice]

Набросал решение "в лоб":

uses crt;
function pack2 (s:string):string;
var n,i:integer;
rs,q:string;
begin
for i:=1 to length (s) div 2 do begin
q:=copy (s,1,i); n:=1;
while copy (s,length(q)*n+1,length(q))=q do inc (n);
if n>1 then begin
str (n,rs); if length (q)=1 then
pack2:=rs+pack2(q)+pack2 (copy (s,length(q)*n+1,255)) else
pack2:=rs+'('+pack2(q)+')'+pack2 (copy (s,length(q)*n+1,255));
exit;
end;
end;
if length (s)<2 then pack2:=s else
pack2:=s[1]+pack2(copy (s,2,255));
end;

function pack (s:string):string;
begin
s:=pack2(s);
while (s<>pack2(s)) and (length(pack2(s))<length (s)) do s:=pack2(s);
pack:=s;
end;

var s:string;
begin
clrscr;
s:='AAAAAAAAAABABABCCD'; writeln (s,' = ',pack(s));
s:='ABABCABABC';                 writeln (s,' = ',pack(s));
end.

На контрольных примерах работает, но по сути есть ошибка, какая - не скажу, чтоб с толку не сбивать

[Bard]

судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.

ты абсолютно прав ... но есть еще одна загвоздка ...

вот она:
если вводиться AAAABBBAAAABBBC то надо выдать 2(4A3B)C
потому что AAAABBBAAAABBBC можно записать как 4A3B4A3BC а эту строку - как 2(4A3B)C...

кстати ,Malice, я не понял твой алгоритм для этой задачи ...

If не трудно then begin объясни пожалуйста; буду очень благодарен; end;...

Добавлено через 10 мин.
Malice, а где же ошибка ... программа проходит через все тесты которые учитель нам дал ...

Сообщение отредактировано: Bard - 11.05.2007 20:39

[Bard]

Malice, ну не томи ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный ...

[Malice]

Malice, ну не томи ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный ...

Ну если устраивает, тогда ладно.. Просто немного коряво с помощью второй функции повторно сжимать, возможны накладки. С алгоритмом то разобрался ?

[Bard]

большое тебе спасибо ... я понял где у тебя глюк ... сейчас подправлю ...

P.S. да с алгоритмом разобрался

Thanks