tossam
tossam - Erectus - 50 Punti
Rispondi Cita Salva
Buona sera.
Sono un informatico e sto lavorando su un algoritmo di compressione dati che si serve della tecnica di string matching ( trovare stringhe uguali) in un vettore di bit.
Dunque specifico già che l'alfabeto dove io lavoro è binario: {0,1}.

Definiamo come stringa da sostituire una qualsiasi stringa che abbia una doppia nel testo.
Ad esempio se nel testo capitasse tre volte banana, io avrei due stringhe da sostituire.
Specifico inoltre che la stringa da sostituire è sempre quella di lunghezza maggiore possibile, ossia se posso sostituire "banana", non devo contare che anche "banan" si ripresenta altre due volte nel testo!
Inoltre devo tenere presente che le stringhe da sostituire hanno una lunghezza minima, oltre alle quali io non posso più sostituire ( altrimenti invece di comprimere espando i dati), cioè se più ricorrenze di "ban", non le conto come stringhe da sostituire, poichè sono sotto il minimo.

Ora: dato il minimo min.
dato l'alfabeto=2, o in generale se preferite k
data la lunghezza del testo len

sapreste trovarmi il numero medio di stringhe sostituibili? e magari la loro lunghezza media?
Come guadagno Punti nel Forum? Leggi la guida completa
In evidenza
Classifica Mensile
Vincitori di novembre
Vincitori di novembre

Come partecipare? | Classifica Community

Community Live

Partecipa alla Community e scala la classifica

Vai al Forum | Invia appunti | Vai alla classifica

mattbit

mattbit Geek 281 Punti

VIP
Registrati via email