Kompresja tekstu - zadanie

Witam
Mam do zrobienia zadanie na spoj-u polegające na jak najlepszej kompresji tekstu. Format kompresji ma wyglądać w taki sposób, że powtarzające się łańcuchy zastępujemy znakiem dodawania + i liczbą liter do zastąpienia (działamy tylko na alfabecie łacińskim) oraz możemy użyć znaku odejmowania - jeżeli chcemy usunąc pewną ilość liter. Przykład:

Wejście:
abcabcabcabdddddd

Wyjście:
abc+3+6-1ddd+3

Wynik:
0.824

Nie proszę o kod, ale o podpowiedź jak się do tego zabrać, czytałem o metodach bezstratnych kompresji, o metodzie LZW, Huffmana, algorytmie ByteRun, ale nie wiem co będzie najlepsze do tego zadania i czy w ogóle zbierałem informacje w dobrym kierunku. Program chciałbym napisać w c99, lub ew. c++ (zdaję sobie sprawę, że w c++ będzie łatwiej, dlatego nie będę się upierał co do czystego c). Nie interesuje mnie wysoki wynik, chciałbym tylko umieć zrobić to zadanie, nauczyć się czegoś nowego.

Bardzo proszę o jakąś pomoc i wskazówki jak zrobić to zadanie.

?
Możesz podać link do zadania, albo pełną treść? Bo mnie sie wydaje że ty masz podany algorytm i masz do zaimplementować, a nie wymyślić jakiś nowy. Ale moge sie mylic.

Oczywiście, oto treśc zadania:

W ramach proekologicznej akcji pod hasłem "szanuj lasy, oszczędzaj papier", Jaś postanowił ograniczyć zużycie papieru w procesie swojej edukacji. Niestety, jego pierwszy pomysł polegający na nieodrabianiu prac domowych spotkał się ze zdecydowaną dezaprobatą nauczycieli. Dlatego też zasmucony Jaś ograniczył się tylko do kompresji pracy domowej i potrzebuje w tym celu Twojej pomocy.

Twoim zadaniem jest skompresowanie podanego na wejściu tekstu pracy domowej, złożonego wyłącznie z małych liter alfabetu 'a'-'z'. Postać skompresowana musi być czytelna dla dekompresora (w który wyposażony został każdy nauczyciel Jasia).

Dekompresor przetwarza tekst znak po znaku, interpretując poszczególne znaki jako polecenia zgodnie z następującymi zasadami:

* znak 'a'-'z': wypisz napotkaną literę,
* znak '+', po którym następuje liczba naturalna n: wypisz ponownie n ostatnio wypisanych liter,
* znak '-', po którym następuje liczba naturalna n: wymaż n ostatnio wypisanych liter. 

Wartość liczby n nigdy nie może przekroczyć liczby dotychczas wypisanych znaków, a łączna liczba wymazywanych znaków nie może przekroczyć trzykrotności długości dekompresowanego pliku.
Wejście

Na wejściu podany jest ciąg znaków 'a'-'z' zakończony znakiem nowej linii, nie dłuższy niż 105 znaków.
Wyjście

Na wyjściu należy wypisać ciąg znaków w skompresowanej postaci. Postać skompresowana musi spełniać założenia podane w treści zadania.
Wynik

Liczba punktów przyznanych za rozwiązanie zadania jest równa stosunkowi długości tekstu skompresowanego do długości tekstu zdekompresowanego.
Przykład

Wejście:
abcabcabcabdddddd

Wyjście:
abc+3+6-1ddd+3

Wynik:
0.824

Pomoze ktos ?:) Bo z checia bym to tez napisal a zupelnie nie wiem jak zaczac...

Zauważ, że to zadanie jest w challenge więc nie ma algorytmu wzorcowego. Zobacz z resztą na wyniki. Najpierw możesz napisać taki program, który będzie kompresował tylko powtarzające się litery po sobie. Potem sądzę, że można by użyć funkcji prefiksowej takiej jak jest w KMP i coś z nią pokombinować.

Konkursy są dla ludzi którzy są wyjątkowi, wybitni, nie dla każdego. Skoro nie masz w ogóle pomysłu jak sie za to zabrać to się ucz. Czytaj książki, rób łatwiejsze zadania i może za jakiś czas będziesz miał pomysł na to zadanie. Jaki to ma sens że ktoś z nas ci je po prostu napisze, albo wymyśli algorytm za ciebie? Masz z tego jakąś satysfakcję że ci doliczy parę punktów?...