[C++] Algoritmo di ricerca pattern in sequenza aleatoria

[gygabyte017]

Ciao a tutti, ho una funzione che genera dei numeri da 0 a 9 ad ogni chiamata in modo casuale (ma sempre uguale, nel senso che facendo ripartire il programma riottengo esattamente le stesse cifre).
Devo scrivere un algoritmo per controllare se la sequenza generata è ciclica o no.

Ad esempio, se la funzione genera 11472181147218114721811472....ecc, e ripete sempre fino a un certo tempo, l'algoritmo deve ritornare 1147218 (probabilmente ciclico), mentre se invece entro un certo tempo non individua nulla, ritorna "probabilmente non ciclico".

Penso sia abbastanza facile da fare, c'è qualcosa di già pronto che posso usare? E se no, mi sapete dare un'idea per farlo in modo efficiente?

Grazie!

[MdE2005]

Codesto è un tipico problema di pattern matching multiplo, molto frequente in certi ambiti IT quali la biologia computazionale proprio per la ricerca di sequenze identiche e/o palindrome in frammenti biologici quali DNA e RNA; affermo ciò perchè se realmente volessi capire quali sono gli algoritmi ottimizzati utilizzati in software dedicati, dovresti indirizzarti verso questo settore.
Come bibliografia, ecco un titolo: Jones - Pevzner, An Introduction to Bioinformatics Algorithms (Computational Molecular Biology).
Per quanto riguarda il problema in sè, può essere affrontato con vari approcci, tra cui:
- Straightforward
- Keyword tree
- Suffix tree
oppure con approcci euristici.

Se invece ti interessa solo una soluzione semplicistica, non ottimizzata, e utile solo per sequenze non lunghissime di caratteri, puoi ricorrere ad algoritmi di brute force: se la lunghezza dei caratteri è un numero dispari, devi considerare solamente sequenze di lunghezza dispari (è evidente che ripetizioni di sequenze di numeri di lunghezza pari non danno mai stringhe di lunghezza dispari); a questo punto prendi come sequenza massima la lunghezza (N-1)/2 (essendo N la lunghezza massima della tua stringa, posta dispari) e provi tutte le combinazioni di numeri nella fattispecie dispari.

Esempio: 123456789745141541514354154514352454131453453343
sequenze da controllare: 123, 234,345.....
12345, 23456, 34567....
fino alla sequenza di lunghezza massima ((N-1)/2).

Spero di essere stato chiaro


Ciao

[gygabyte017]

Grazie mille, davvero molto esaustivo!

ciao