Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> Rozumiem że nie chodzi Ci o podciągi tylko o sekwencje (tzn. M bajtów
> ze sobą sąsiaduje).

Owszem. Jeżeli tak ci łatwiej. (W zasadzie można nawet to sformułować: "mamy
ciąg N liczb naturalnych mniejszych niż K, znajdź liczbę pojawiającą się
najczęściej". Oczywiście N wynosi prawie bilion, K równe jest 2^128 , jedyne
dozwolone operacje to te, które może wykonać maszyna pana T. a liczby
zapisane są binarnie. )

> "M jest np. 16" oznacza, że możliwych kombinacji jest (zawrotne) 256.

Dla 16 bajtów... można mieć tylko 256 różnych liczb 128-bitowych? Ciekawe!
Nie pomyślałem! ;)

> Napisz jaką dopuszczasz złożoność pamięciową ("nie mieć w całości w RAM"
> to naprawdę biedna informacja).

Ok, załóżmy że plik jest 1GB, a RAM mamy 10 razy mniej, czyli 128 MB - i nie
ma że jakaś wirtualna czy coś. Ewentualnie 100 GB plik i 10 GB RAM.

Uwaga: zakładamy że algorytm jest jawnie znany i że dostaniemy możliwie
"złośliwie skomponowany" plik - czyli najgorszy przypadek (jakkolwiek byłby
on małoprawdopodobny).

I chcemy mieć coś fajniejszego niż np. czytanie pliku 16 razy. (Za pierwszym
ustalamy jaki jest pierwszy bajt, za drugim jaki drugi, ...) Powinno wymagać
najwyżej 2-krotnego czytania pliku. Najlepiej 1-krotnego.

> Jeśli dodefiniujesz problem i będę miał chwilę czasu, to pokaże Ci, jak
> bardzo deprecjonujesz kartkę i długopis...

Dodefiniowałem.

Ja nie deprecjonuję kartki - tylko deprecjonuję zwykły długopis. Ołówek jest
lepszy!

Nota bene, jeden z fajniejszych gadgetów, to elektroniczny notes - pisze się
normalnie na zwykłym papierze A4, jednocześnie "w tle" robi się PDF z tym co
napisane (wektorowo). Pamięci (karta SD) ma to na kilkadziesiąt tysięcy
stron, działa bez i z komputerem, a jeszcze może służyć i za zwykły tablet.