Discussion :

[madprod]

Bonjour,

J'ai un liste ordonnées de mots :
1. machin
2. bidule
3. truc
4. machin
5. chose
6. truc
7. machin
8. chose
9. truc
10. machin
11. chose
12. bidule
13. truc
14. truc
15. machin
16. chose

Je souhaite identifier la plus grande séquence de mots qui se répète au moins une fois consécutivement. Par exemple ici, on a la séquence "truc / machin / chose" qui est répétée 2 fois (l'original en 3 et les répétitions en 6 et 9).
Dans une séquence, un même mot ne peut apparaitre au plus q'une seule fois.
La liste contient au plus une centaine de mots.

Voila, tout est dit, sinon qu'avec mes faibles connaissances en algorithmique, je ne sais pas comment faire !

[plawyx]

ce n'est pas un problème lié à java !

[Carhiboux]

Mais il souhaite peut être le faire en Java! :p

Là tout de suite, intuitivement, j'aurais tendance à passer par un arbre.

genre :

pour chaque mot:
Si il n'est pas encore un enfant de la racine, on l'ajoute.
On regarde ses prédécesseurs (si il y en a) et on l'ajoute comme enfant des séquences formées par ses prédécesseurs.

Et par dessus cela, tu dois gérer un compteur pour chaque feuille. A chaque fois que tu retrouve la séquence, tu incrémentes ce compteur.

[madprod]

Mais il souhaite peut être le faire en Java! :p

Là tout de suite, intuitivement, j'aurais tendance à passer par un arbre.

genre :

pour chaque mot:
Si il n'est pas encore un enfant de la racine, on l'ajoute.
On regarde ses prédécesseurs (si il y en a) et on l'ajoute comme enfant des séquences formées par ses prédécesseurs.

Et par dessus cela, tu dois gérer un compteur pour chaque feuille. A chaque fois que tu retrouve la séquence, tu incrémentes ce compteur.

Donc à la fin l'arbre représente toutes les séquences qu'on aura trouvé. On n'a plus qu'à chercher la feuille la plus profonde pour savoir quelle est la séquence la plus longue c'est ça ?
Comment prendre en compte le fait qu''une séquence doit être répétée sans "trou" ?