[algorytmika] problem odpowiedniości słów

[niewinnosc]
Jeśli dział dla zaawansowanych, to:
Mamy taki o to zaawansowany problem <font color="darkblue">decyzyjny</span> o nazwie "problem odpowiedniości słów":

Dane wejściowe:
<font color="darkblue">alfabet</span> S
dwa równoliczne ciągi <font color="darkblue">słów nad alfabetem</span> S, X(x1,x2,...,xn) i Y(y1,y2,...,yn).
Wynik:
Tak - jeśli istnieje taki ciąg indeksów I(i1,i2,...,ik) taki, że xi1,xi2,...,xik=yi1,yi2,...,yik.
Nie - w przeciwnym wypadku.

Wprowadźmy kilka formalnych definicji:
problem decyzyjny - problem, którego wynikiem jest odpowiedź tak albo nie.
alfabet - niepusty i skończony zbiór symboli
słowo nad alfabetem - dowolny skończony ciąg liter tego alfabetu

przyjmijmy następującą konwencję zapisu:
słowo s=(s1,s2,...,sn) będziemy zapisywać po prostu jako s1s2...sn
np. słowo s=(b,c,c,a,b) będziemy zapisywać jako "bccab"
{uwaga - aby w takim zapisie słowo było jednoznacznie, musimy nałożyć na alfabet pewne dodatkowe ograniczenia, o których tu nie wspomnę, aby nie zaciemniać obrazu}

Przykład: Mamy trzyliterowy alfabet S={a,b,c}. Istnieje nieskończenie wiele słów nad alfabetem S, w tym: bccab, abc, a, aa, aaa, aaaa, ...

Ostatecznie powracając do samego problemu, oto dwa przykłady:
Przykład 1)
alfabet S = {a,b}

     1       2               3         4

X a b aa ab
Y aa abaa b a

W powyżyszym przykładzie wynik to "tak", ponieważ np. ciąg indeksów (4,3,1,1) generuje w obydwu ciągach X i Y to samo słowo - abaaaa

Wystarczy jednak, że odrobinę zmienimy ciągi X i Y, np.
Przykład 2)
alfabet S = {a,b}

     1        2                 3           4

X aa b aa ab
Y a abaa b a

Odpowiedzią jest "nie", gdyż można wykazać że nie istnieje taki ciąg indeksów, który generuje to samo słowo w X i Y.

Jak zwykle, czekam na wszelkie obserwacje i szkice algorytmów.
Pozdrawiam.
[niewinnosc]

p.s. prawdopodobnie, temat ten znajdzie swój finał w artykule o złożoności obliczeniowej i klasach rozwiązywalności problemów.

Chyba zrobiłeś literówkę w tym drugim przykładzie, bo wydaje mi się, że jednak istnieje taki ciąg indeksów:
1,2,3,2,4,1,1,1

A teraz spróbuję przedstawić pseudoalgorytm, jakim się posługiwałem przy wyszukiwaniu tego ciągu (pseudo, ponieważ nie spełnia jedego z założeń algorytmu - nie ma pewności, że rozwiązanie zostanie znalezione w skończonym czasie).
Ciężko jest mi opisać słowami algorytm. Pewnie łatwiej byłoby napisać procedurę, ale spróbuję.
Algorytm wybitnie rekurencyjny:

1. i = 1. r = (zbiór pusty). s1 = s2 =;
2. Dla każdego i-tego słowa z ciągu X wybieramy warość i sprawdzamy możliwości.
3. Szukamy w ciągu Y takiego słowa, żeby r+xi było początkiem słowa drugiego ciągu. Jeżeli znajdujemy to do s1 dopisujemy xi do s2 dopisujemy yi. Wyszukujemy wszystkie możliwe pasujące słowa. Jeżeli nie znajdziemy to ta cześć algorytmu się kończy.
4. Jeżeli ciąg s2 jest dłuższy niż s1 to reszta r = s2 - s1 (jest tym fragmetem o jaki jest dłuższe s2) i powtarzamy punkt 2 i 3, ale zamieniając x z y i X z Y (nie chce mi się przepisywać).
5. Jeżeli ciąg s1 jest dłuższy to analogicznie jak w 4 tylko że nie zamieniamy X i Y.
6. Jeżeli s1 = s2 to mamy odpowiedź tak.

Pozostaje jeszcze możliwość, że ciąg będzie w nieskończoność się rozszrzał. Np. przy fragmencie alfabetu:
1
X a
Y aa
i potrzebujemy dopasować:
a, a,...
aa, aa, aa...
wówczas proponuję zakończyć przetwarzanie tej części rekurencyjnej w momencie, gdy różnica w długości powstałych ciągów przekroczy długość najdłuższego słowa w alfabecie (to jedyny haczyk. W ty miejscu można się "zawiesić")

Nie wiem czy dobrze to przedstawiłem. Chyba lepiej będzie jak napiszę jakiś psedokod to może coś zrozumiecie z mojego bełkotu. Biorę się do pisania.

Prawdę mówiąc, nie popełniłem literówki - tylko merytoryczny błąd! Nie mniej nie będę poprawiał tamtego postu, aby zachować ciąg rozumowania.

tak więc - odpowiedzią na Przykład 2) jest "tak" bo ciąg 1,2,3,2,4,1,1,1 spełnia zadanie.

W tej chwili jestem w szkole, i z przyjemnością zanalizuję twój algorytm, po powrocie do domu.

Natomiast wyznaczam dodatkowe zadanie pomocnicze - musimy opracować kilka szczególnie przydatnych zestawów danych wejściowych. Takich czytelnych ilustracji (w szczególności w tej chwili nie mamy jeszcze żadnego przykładu którego odpowiedzią jest "nie").

Przypomina mi to tą pamiętną przygodę z optymalizowaniem ułożenia okręgów na półpłaszczyźnie.

Tak więc - czekam na czytelne przykłady na "tak" i na "nie". Doświadczenie uczy, że szczególnie owocne jest wnioskowanie oparte o przykłady danych wejściowych.

gorąco pozdrawiam
[niewinnosc]

[b]NIE[/b]:

S = {a;b}

   1

X = a
Y = b

Nad algorytmem to się pomyśli jeszcze :)

Świetnie - Vogel - prawdopodobnie to jest właśnie najprostszy przykład na "nie". Spróbujmy może odrobinę go opisać:

Jeżeli nie istnieje chociażby jedna para xi, yi - taka że xi i yi zaczynają się od tej samej litery - odpowiedź brzmi "nie". [Chociażby dlatego, że nie można w ogóle rozpocząć budowania słów]

Moje przykłady:

3)NIE:
S={a,b}
X=(a,bbb)
Y=(ab,b)

4)TAK:
S={a,b}
X=(a,bb)
Y=(ab,b)
oczywiście I=(1,2)

5)NIE:
S={a,b,c}
X=(ab,bc)
Y=(ac,ba)

NIE
S={a,b}
X={ab,aba,bba,bab}
Y={bbab,aabb,abba,ba}

heheheh to mój pierwszy post na tym forum @Baranek@ (młodszy Dry)

heh ale pranie mozgu robicie,
zaryzykuje twierdzenie sa dwa przypadki przy ktorych zawsze wynikiem jest TAK:

1. S= {dowolne}
   X=Y;
   przy dowolnym I wynikiem jest zawsze TAK;

2. a teraz rebus - pokazcie drugi przypadek przy ktorym jest zawsze
   TAK ??? :-)

Moim zdaniem czepiacie się trochę szczegółów (ja bez problemu zrozumiałem :) )
Poza tym tu nie chodzi po przypadki tylko o stwierdzenie każdorazowe.
Ale skoro jesteśmy już przy tym temacie to przedstawię wam jeszcze moje eksperymenty (jak zdążę dziś i znajdę swoje notatki, na razie z pamięci piszę, więc może być źle)
Mamy alfabet S = {a, b} oraz dwa ciągi słów nad alfabetem
X = (a, b, ab)
i
Y = (aa, a, bb),
przy czym załóżmy, że żadne słowo w tym ciągu nie ma więcej niż 2 symboli (tak na początek, dla łatwiejszego tłumaczenia).
Najpierw zróbmy listę wszystkich możliwych układów tych symboli:
a
b
aa
ab
ba
bb
(pewnie łatwiej byłoby z 0 i 1, ale...)
Teraz utwórzmy po 2 tablice reszt, dla każdego zbioru ciągów X i Y.
Oznaczmy przez Xp tablicę w której będziemy mieli wszystkie możliwe produkowane reszty przez X (czyli wszystkie ciągi, jakie można otrzymać z każdego słowa biorąc od prawej).
Dla każdego słowa (kolumny) wstawiamy znak T jeżeli możliwe jest otrzymanie takiej reszty jak jest w wierszu i F jeżeli nie
Xp
1 2 3
a T N N
b N T T
aa N N N
ab N N T
ba N N N
bb N N N
Analogicznie dla drugiego ciągu Y:
Yp
1 2 3
a T T N
b N N T
aa T N N
ab N N N
ba N N N
bb N N T

Teraz analogicznie reszty akceptowane (tzn. wszystkie ciągi, jakie można utworzyć od prawej)
Xa
1 2 3
a T N T
b N T N
aa N N N
ab N N T
ba N N N
bb N N N
Analogicznie dla drugiego ciągu Y:
Ya
1 2 3
a T T N
b N N T
aa T N N
ab N N N
ba N N N
bb N N T

Dobra znalazłem część notatek (dlaczego ja zawsze wszystko mam w częściach?)
Mamy te 4 tablice:
Xp Yp
1 2 3 1 2 3
a T N N T T N
b N T T N N T
aa N N N T N N
ab N N T N N N
ba N N N N N N
bb N N N N N T
Ya Xa
1 2 3 1 2 3
a T T N T N T
b N N T N N N
aa N N N T N N
ab N N T N N T
ba N N N N N N
bb N N T N N N

Teraz z naszych ciągów możemy zacząć budować ciąg na 3 sposoby:
Od pierwszego indeksu:
X:a|
Y:aa|
Od drugiego indeksu:
X:b|
Y:a|
Od trzeciego indeksu:
X:ab|
Y:bb|

Z tego od razu widać, że tylko pierwszy indeks może zaczynać nasz ciąg. Reszta z tego indeksu to 'a' i produkuje ją Y.
Teraz zadanie to tak chodzić po naszych tablicach, żeby reszty produkowane przez jeden ciąg mogły być akceptowane przez drugi.
W tym wypadku w Xa musimy znaleźć słowo akceptujące 'a'. W naszym przykładzie to 1 i 3 słowo.
Teraz największy problem to tak dopasować metodę przechodzenia po tablicy, żeby odpowiadała ona prawdziwej metodzie dopasowywania końcówek. Odpowiednio nakładając na siebie tablicę (ew. tworząc jeszcze tablice różnic pomiedzy słowami w X i Y) powinniśmy otrzymać metodę wyznaczającą, czy istnieje rozwiązanie tego problemu (niestety jeszcze muszę nad tym popracować, bo dla niektórych przypadków dotychczasowe moje metody sypią się). Mam nadzieję, że ktoś z was wpadnie na odpowiedni pomysł.

Wczoraj wieczorkiem wymodziłem taki programik .
Bardzo prosze o wyrozumiałość , ponieważ ja programuje od niecałych 10 miesięcy więc nie krzyczcie jak coś będzie źle , bo ja sie po prostu ucze ;) . Wiem , że nie wygląda on zbyt ładnie , nie analizowałem go zbyt długo bo za 2 dni mam egzamin [stuk] , więc może mieć błędy .
[code]#include
#include
#include
#include
#include
#define n 4 //tu sie ustwia dlugosc slowa
#define max 20 //tu sie ustwia maxymalna dlugosc utworzonego ciagu

const char *wyrazX[n]={"aa","b","aa","ab"}; //tu definiujemy slówka
const char *wyrazY[n]={"a","abaa","b","a"};

int funkcja(char*,char*,int*,int*);

int main()
{
char newx[max+10]; //nowo powstajace słowo z liter słowa x
char newy[max+10]; //nowo powstajace słowo z liter słowa y
int tablica[max+1]; //tablica zapamietuje ktore litery wykorzystano
int indeks=0;
newx[0]='\0';
newy[0]='\0';
clrscr();
funkcja(newx,newy,tablica,&indeks);
cout !

Wczoraj wieczorkiem wymodziłem taki programik .
Bardzo prosze o wyrozumiałość , ponieważ ja programuje od niecałych 10 miesięcy więc nie krzyczcie jak coś będzie źle , bo ja sie po prostu ucze ;) . Wiem , że nie wygląda on zbyt ładnie , nie analizowałem go zbyt długo bo za 2 dni mam egzamin [stuk] , więc może mieć błędy .
[code]#include
#include
#include
#include
#include
#define n 4 //tu sie ustwia dlugosc slowa
#define max 20 //tu sie ustwia maxymalna dlugosc utworzonego ciagu

const char *wyrazX[n]={"aa","b","aa","ab"}; //tu definiujemy slówka
const char *wyrazY[n]={"a","abaa","b","a"};

int funkcja(char*,char*,int*,int*);

int main()
{
char newx[max+10]; //nowo powstajace słowo z liter słowa x
char newy[max+10]; //nowo powstajace słowo z liter słowa y
int tablica[max+1]; //tablica zapamietuje ktore litery wykorzystano
int indeks = 0;

newx[0] = '\0';
newy[0]='\0';
clrscr();
funkcja(newx,newy,tablica,&indeks);
cout !

Wczoraj wieczorkiem wymodziłem taki programik .
Bardzo prosze o wyrozumiałość , ponieważ ja programuje od niecałych 10 miesięcy więc nie krzyczcie jak coś będzie źle , bo ja sie po prostu ucze ;) . Wiem , że nie wygląda on zbyt ładnie , nie analizowałem go zbyt długo bo za 2 dni mam egzamin [stuk] , więc może mieć błędy .
#include
#include
#include
#include
#include
#define n 4 //tu sie ustwia dlugosc slowa
#define max 20 //tu sie ustwia maxymalna dlugosc utworzonego ciagu

const char *wyrazX[n]={"aa","b","aa","ab"}; //tu definiujemy slówka
const char *wyrazY[n]={"a","abaa","b","a"};

int funkcja(char*,char*,int*,int*);

int main()
{
char newx[max+10]; //nowo powstajace słowo z liter słowa x
char newy[max+10]; //nowo powstajace słowo z liter słowa y
int tablica[max+1]; //tablica zapamietuje ktore litery wykorzystano
int indeks=0;
newx[0]='\0';
newy[0]='\0';
clrscr();
funkcja(newx,newy,tablica,&indeks);
cout !

Witam.

Ojejku ale ktoś tu narobił bałaganu ...

Wczoraj wieczorkiem wymodziłem taki programik

Jak jeszcze raz zobaczę ten tekst to oszaleję.
:-8

a teraz na poważnie ...
Trouble - wybacz że będę dosłownie cytował twoją wypowiedź ale zaatakowałeś mnie w kilku punktach:

Witam ! Na początku napisałeś , że :
słowo nad alfabetem - dowolny skończony ciąg liter tego alfabetu
oraz , że
X(x1,x2,...,xn)
Skoro słowo jest ciągiem liter z alfabetu , to czemu potem opisujesz je jako ciąg ciągów liter alfabetu , np. przykład 1 :
1 2 3 4
X a b aa ab
to słowo składa sie z 2 ciągów 1-literowych i z 2 ciągów 2-literowych .

Twoja wypowiedź świadczy o tym, że zbyt długo się nie wczytywałeś w treść problemu. Spróbuję wypunktować twój problem Trouble:

słowo nad alfabetem - dowolny skończony ciąg liter tego alfabetu
dane wejściowe - dwa równoliczne ciągi słów nad wspólnym alfabetem

Co tu jest niezrozumiałe i sprzeczne?
Jak sam prawdopodobnie rozumiesz - dane wejściowe do tego problemu to ciąg słów (a dokładnie to dwa ciągi słów), gdzie słowo to ciąg liter.

W problemie odpowiedniości słów mamy do czynienia z ciągami którego elementy to ciągi.

1 2 3 4
X a b aa ab
to słowo składa sie z 2 ciągów 1-literowych i z 2 ciągów 2-literowych .

nie prawda od samego początku - X to nie jest słowo tylko ciąg słów.

(Oczywiście ciąg słów też jest słowem co można udowodnić chociażby indukcyjnie - niemniej z punktu widzenia problemu lepiej mówić o ciągach słów)

Na początku napisałeś też , że zarówno X jak i Y mają po n wyrazów w ciągu , więc w tym przypadku , n=4 a to jest różne od 6 ( tyle jest liter w słowie ).

oczywiście konsekwentnie jesteś w błędzie:

X i Y to ciągi po 4 słowa,
np. X to ciąg składający się z następujących 4 słów:
słowo 1) a
słowo 2) b
słowo 3) aa
słowo 4) bb

gdzie każde słowo to niepusty ciąg liter alfabetu {a,b}

<quote>Więc tak naprawde słowo składa się z ciągu ciągów liter z alfabetu , X(x1,x2,...,xn) gdzie xi jest ciągiem liter , 0!

tablica reszt od prawej:
(...)

Dlaczego ja tak łatwo nie potrafię tłumaczyć...

Brutalna siła - czyli sprawdzamy wszystkie możliwości ... tylko jak wtedy ocenić że odpowiedzią jest NIE? - w której chwili przestać dalsze budowanie.

Nie. Raczej chodzi mi o system wzajemneto położenia T i N. Traktowanie tego jak pewnego rodzaju graf zorientowany.

Co więcej, mój wysiłek nie skłania się do rozwiązania tego problemu tylko raczej zbudowania formalnego matematycznego dowodu na to, że taki algorytm istnieć nie może ...

Jestem optymistą :) Jeżeli nawet nie można w 100% to chciałbym mieć przynajmniej coś takiego jak przedstawiony test Rabina-Milera. Ten problem odpowiedności słów może mieć wiele praktycznych zastosowań (choćby w szyfrowaniu).

Witam !
Po pierwsze nikogo nie atakowałem , tylko chciałem wyjaśnić kilka kwestii . Oczywiście mój błąd , bo zupełnie nie miałem racji . Masz racje . Wynika to z tego , ze niedokładnie przeczytałem sam początek problemu . Ale zamiast mnie ośmieszać i czepiać sie do tego samego przez kilakdziesiąt linijek wystarczyło mi tylko pokazać to :
<font color="violet">Dane wejściowe:
alfabet S
dwa równoliczne ciągi słów nad alfabetem S, X(x1,x2,...,xn) i Y(y1,y2,...,yn). </span>
Oczywiście też mój program jest tu zupełnie nie na miejscu , głupio mi że wyskoczyłem z czymś takim banalnym w tym dziale , ale jak napisałem na samym początku :
<font color="violet">Bardzo prosze o wyrozumiałość , ponieważ ja programuje od niecałych 10 miesięcy więc nie krzyczcie jak coś będzie źle , bo ja sie po prostu ucze </span>
A twoja odpowiedź na moją prośbe była następująca :
<font color="violet">Buachachacha</span>
...
No cóż , będę miał nauczke na przyszłość żeby czytać uważnie pytania i problemy . Bardzo przepraszam , że tak zaśmieciłem ten temat , ale serio nie moge skasowac tych postów . Rozumiem , że nie jestem tu juz mile widziany ( bo to przecież forum dla zaawansowanych ) , więc nie będe sie udzielał juz w tym temacie

No cóż , będę miał nauczke na przyszłość żeby czytać uważnie pytania i problemy . Bardzo przepraszam , że tak zaśmieciłem ten temat , ale serio nie moge skasowac tych postów . Rozumiem , że nie jestem tu juz mile widziany ( bo to przecież forum dla zaawansowanych ) , więc nie będe sie udzielał juz w tym temacie

Kapustce na pewno nie chodziło o atakowanie Ciebie. Wystarczy, że będziesz czytał problemy i będzie grać.
Co do postów to się nie martw, bo Adam na pewno je usunie (łącznie z tymi zbędnymi dyskusjami).
A w dziale zaawansowanych i w tym temacie to proszę bardzo udzielaj się jak najczęściej. Im więcej pomysłów tym lepiej.

Trouble - na pewno ośmieszanie Ciebie to była ostatnia rzecz którą zamierzałem zrobić ...

Zwyczajnie za szybko usiadłeś do pisania programu, uprzednio nie wczytując się w sam problem - zdarza się.

Naprawdę nic się nie stało i bardzo pogodnie patrzę na Twoje dalsze propozycje i uwagi dotyczące tego problemu.

Pozdrawiam

Wróćmy więc do problemu, który mi żyć nie daje...
Teraz jeszcze inny sposób. Ta metoda jednak zawsze zakończy się w skończonym czasie, więc można to już nazwać algorytmem. Z tym, że złożoność obliczeniowa eliminuje to z praktycznych zastosowań (wykładniczo-wykładniczo-wykładnicza [stuk] )
Dobrze przyjmijmy oznaczenia:
S - alfabet
X, Y - ciągi słów nad alfabetem
n - liczba symboli w alfabecie
l - długość najdłuższego słowa
k - liczba słów w ciągach
s = (l-1)ln-1 - najdłuższa możliwa reszta
L - lista wszystkich możliwych wariacji z powtórzeniami z n symboli branych maksymalnie po s ze znakami '+' oraz '-' oraz elementem 0. [liczba elementów listy 2n*(1-ns)/(1-n) ]
R - tablica reszt z k kolumnami i wierszami indeksowanymi przez listę L.
Każde pole R[i, j] tablicy tworzymy według algorytmu:
I Bierzemy j-te słowa z obydwu ciągów X i Y (X[j] i Y[j])
II Bierzemy i-te słowo z listy L (L[i])
1. Jeżeli L[i] ma znak '+' to do słowa z X dopisujemy z lewej strony L[i] bez znaku (x := L[i]|X[j]; y := Y; gdzie '|' jest operatorem konkatenacji)
2. Jeżeli L[i] ma znak '-' to do słowa z Y dopisujemy z lewej strony L[i] bez znaku (x := X; y := L[i]|Y[j])
3. Jeżeli i = 0 to nie dopisujemy nic (x := X; y := Y)
III. Jeżeli z powstałych dwóch słów Length(x)>Length(y) (gdzie Length jest funkcją zwracającą długość ciągu), to:
1. Sprawdzamy czy y zawiera się w x patrząc od lewej (Left(x, Length(y)) = y; gdzie Left jest funkcją Left(S, C) zwracającą C znaków z S biorąc od lewej).
a. Jeżeli nie zawiera się to R[i, j] := -1;
b. Jeżeli zawiera się to bierzemy resztę r z x (r := Right(x, Length(x)-Length(y); gdzie Right jest funkcją Right(S, C) zwracającą C znaków z S biorąc od prawej) z '+' i w R[i, j] wpisujemy indeks tego słowa z listy L. Jeżeli nie ma takiego słowa na liście to wpisujemy R[i, j] := -1;

w przeciwym wypadku:
2. Sprawdzamy czy x zawiera się w y patrząc od lewej (Left(y, Length(x)) = x).
a. Jeżeli nie zawiera się to R[i, j] := -1;
b. Jeżeli zawiera się to bierzemy resztę r z y (r := Right(y, Length(y)-Length(x)) z '-' i w R[i, j] wpisujemy indeks tego słowa z listy L. Jeżeli nie ma takiego słowa na liście to wpisujemy R[i, j] := -1;

A teraz sam algorytm wyszukiwania.

1. Zaczynam od wiersza 0 tablicy.
2. Dla każdego pola tablicy różnego od -1 sprawdzamy wiersz, który wskazuje, jednocześnie wstawiając -1 w miejsce odczytanego pola.
3. Jeżeli trafimy na odwołanie na wiersz nr 0, to nasz algorytm odnalazł ciąg (odpowiedź TAK)
4. Jeżeli nasz algorytm nie będzie mógł wybrać żadnego pola (wszystkie pola w wierszu = -1) to algorytm nie znalazł ciągu (odpowiedź NIE).

Dwa szczególne przypadki, które mogą odrobinę przyspieszyć wyszukiwanie to:

1. W wierszu 0 nie ma innych elementów jak -1 (brak rozwiązania)
2. W tablicy nie ma elementu o wartości 0 (brak rozwiązania)

Teraz kilka słów wytłumaczenia.
Tablica ma skończony rozmiar, a dzięki temu, że usuwamy elementy (wpisujemy -1) mamy pewność, że wykonywanie algorytmu się skończy.
Najwięcej kontrowersji budzi zapewne ograniczenie liczby wierszy do 2n(1-ns)/(1-n) oraz liczba najdłuższej reszty. Pierwsza liczba to po prostu wszystkie możliwe wariacje max s elementowe z n znaków (suma ciągu geometrycznego).
Druga liczba s = (l-1)*ln-1 jest bardziej kłopotliwa. Szczerze mówiąc to otrzymałem ją metodą empiryczną dopasowując wzór do danych doświadczalnych. Nie potrafię przedstawić sposobu w jaki mój mózg do tego doszedł, ale przy danej długości słowa l, oraz liczby znaków n potrafię przedstawić takie ciąg słów, że nie można z nich ułożyć dwóch takich samych ciągów, że reszta będzie krótsza. Jednocześnie nie znalazłem też takiego ciągu, w którym mogłaby być dłuższa reszta (jeżeli taka istnieje to da się ją skrócić). Jeżeli ktoś mi przedstawi takowy to oczywiście swoje oszacowanie poprawię.

Dobrze teraz pomęczcie się i znajdźcie przykład rozkładający ten algorytm :-D