Algorithmie, recherche de sous chaînes
Bonjour à tous,
Je dois développer un logiciel qui a partir d'un code est en mesure de l'analyser afin de me ressortir différentes caractéristiques.
Je dispose de différents produits et equipements possédant chacun une référence. Cette référence est une partie de mon code final. Un code est donc l'assemblage de plusieurs références.
Comme un exemple est plus parlant une démonstration :
J'ai le code : FMR-62-H1
J'ai les produits :
Code 1 : FM
Code 2 : F ou R
Code 3 : de 4 à 9
Code 4 : de 1 à 4
Code 5 : H ou M
Code 6 : 1 ou 2
Un code valide doit être la combinaison d'une et une seule suite de code (soit code 1 à code X).
Analyser la chaîne dans le cas simple c'est à dire, je cherche le PREMIER MOTIF TROUVE, puis je continue est assez facile à implémenter.
Mais comment gérer les cas où il faut effectuer des retours en arrière ?
Exemple : FMR5
Code 1 : F ou FM
Code 2 : M ou R
Code 3 : 5
Ici le problème va se situer au niveau du code 1, mon algo va voir que F correspond au premier motif de la chaîne et en continuant en code 2 se rend compte qu'il n'y a plus de solution. Comment gérer le "retour en arrière" ?
Un exemple de code déjà réalisé (ne gère que les chaînes simples):
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public boolean analyse(Code code) {
int indice = 0;
int tailleMotif = 1;
int tailleMaxMotif = 3;
int tailleCode = code.getCode().length();
String motif = "";
boolean codeValide = true;
while(indice < tailleCode && codeValide) {
//recherche de motifs dans la chaine suivant une taille maximum
for(tailleMotif = 1; tailleMotif < tailleMaxMotif; tailleMotif++) {
motif = code.getCode().substring(indice, indice+tailleMotif); //récupération du motif
//si le motif existe on sort de la boucle de vérification du motifs
if(existe(motif)) {
indice += tailleMotif;
break;
}
else if(tailleMotif == tailleMaxMotif-1) {
codeValide = false;
}
}
}
return codeValide;
} |
J'ai essayé d'être le plus clair possible, si vous avez besoin de plus de précisions n'hésitez pas.
Merci d'avance.
