Détecter des patterns

[Lovmy]

Bonjour,

Imaginons cette suite de chiffre:

4 67 23 88 34 90 23 88 65 3 9 23 88 77 12 3 99 00 11 23 99 00 34 78 56 99 00 34 12

J'aurais voulu savoir si quelqu'un a déjà écrit un algorithme capable de détecter des, on va dire redondances, dans une suite de chiffres ?

En gros un algo qui me dit, sans même connaitre les chiffres recherchées, dans cette suite j'ai trouvé trois, heu je sais pas comment l'exprimer, genre voila j'ai trouvé un 23 88 - 99 00 imbriqué dans un autre 23 88 - 99 00 imbriqué dans un autre 23 88 - 99 00 (je sais pas si je me fais bien comprendre c'est un peu spécial comme truc )

Pouvez-vous m'aider, si du moins vous comprenez ce que je recherche

Merci par avance !

[pseudocode]

Détecter les "imbrications" sans savoir qu'on cherche des imbrications, ca va être assez compliqué.Dans ton exemple, on pourrait aussi dire qu'on a trois "23 88", suivi de trois "99 00".

1ère étape, à mon avis, c'est de repérer les séquences de 2 valeurs qui se répètent. Construire une matrice de co-occurrence est un bon moyen.

2nde étape, remplacer les séquences de 2 valeurs qu'on a trouvé par une seule valeur "spéciale", et recommencer l'étape 1. Ca permet ainsi de trouver des séquences de 3 valeurs qui se répètent.

etc.

[zamato]

Il existe des algorithmes efficaces qui permettent trouver les plus grandes séquences qui se répètent au moins R fois dans la suite. En O(N log N) si ta suite a N chiffres.

Après ça dépend ce que tu recherches, les plus grandes séquences qui se répètent, les séquences qui se répètent le plus souvent etc...