// Time-stamp: /** * Quelques algorithmes de recherche de motifs * - Algorithme naïf * - Algorithme de Morris et Pratt * - Algorithme de Knuth, Morris et Pratt * @author O. Carton * @version 1.0 */ class Pattern { /** * Programmation naïve de la recherche d'un motif. * Pour chaque position possible du motif dans le texte, * on teste si cette position est une occurrence du motif. * Ce test est effectué en comparant les caractères du motif * avec les caractères du texte de gauche à droite. * Si tous les caractères du motifs sont égaux aux caractères * du texte aux positions correspondantes, une occurrence a * été trouvée et la position de cette occurrence est retournée. * Sinon, la recherche se poursuit en passant à la position * suivante. * @param pattern motif à rechercher * @param text texte dans lequel le motif est recherché * @return position de la première occurrence si le motif a au moins * une occurrence dans le texte et -1 sinon. */ static int naive0(String pattern, String text) { int m = pattern.length();// Longueur du motif int n = text.length(); // Longueur du texte int i = 0; // Position dans le motif int j = 0; // Position dans le texte int k; // Position du motif dans le texte // La variable k parcourt toutes les positions possibles du // motif dans le texte. La position du motif est repérée par // la position de sa première lettre. for (k = 0; k < n-m+1; k++) { i = 0; // Début du motif j = k; // Position dans le texte // Test d'une occurrence en position k while (i < m && pattern.charAt(i) == text.charAt(j)) { // Si les deux caractères coïncident, // les deux curseurs avancent d'une position vers la droite. i++; j++; } if (i == m) // Occurrence trouvée en position k return k; } // Aucune occurrence return -1; } /** * Programmation naïve de la recherche d'un motif. * Cette méthode est obtenue en remarquant que dans la méthode * précédente, la variable k contient toujours la valeur de j-i. * Par conséquent, la variable k peut être supprimée. * @param pattern motif à rechercher * @param text texte dans lequel le motif est recherché * @return position de la première occurrence si le motif a au moins * une occurrence dans le texte et -1 sinon. */ static int naive(String pattern, String text) { int m = pattern.length();// Longueur du motif int n = text.length(); // Longueur du texte int i = 0; // Position dans le motif int j = 0; // Position dans le texte while (i < m && j-i < n-m+1) if (pattern.charAt(i) == text.charAt(j)) { // Si les deux caractères coïncident, // les deux curseurs avancent d'une position vers la droite. j++; i++; } else { // Sinon la fenêtre avance d'une position. // j retourne à la position à droite du début de la fenêtre // i retourne au début motif. j = j-i+1; i = 0; } if (i == m) // Occurrence trouvée en position j-i return j-i; else // Aucune occurrence return -1; } /** * Recherche d'un motif avec l'algorithme de Morris et Pratt. * @param pattern motif à rechercher * @param text texte dans lequel le motif est recherché * @return position de la première occurrence si le motif a au moins * une occurrence dans le texte et -1 sinon. */ static int morrisPratt(String pattern, String text) { int m = pattern.length();// Longueur du motif int n = text.length(); // Longueur du texte int[] s = new int[m]; // Fonction de suppléance int i; // Position dans le motif int j; // Position dans le texte // Calcul de la fonction de suppléance s // Pour tout i > 0, s[i] est la longueur bord maximal du // préfixe de longueur i du motif, c'est-à-dire p_0 ... p_{i-1}. // Pour un préfixe w du motif, on a |bord(w)| = s[|w|]. // On a donc |bord^2(w)| = s[|bord(w)|] = s[s[|w|]]. // Les longueurs des bords d'un préfixe w sont donc les valeurs // s[|w|], s[s[|w|]], s[s[s[|w|]]] ... s[0] = i = -1; for (j = 1; j < m; j++) { // Ici i = s[j-1] while (i >= 0 && pattern.charAt(i) != pattern.charAt(j-1)) i = s[i]; // Ici i = s[j]-1 s[j] = ++i; } // Recherche du motif i = 0; j = 0; while (i < m && j < n) { if (pattern.charAt(i) == text.charAt(j)) { // Si les deux caractères coïncident, // les deux curseurs avancent d'une position vers la droite. j++; i++; } else { if (i == 0) j++; else i = s[i]; } } if (i == m) // Occurrence trouvée en position j-i return j-i; else // Aucune occurrence return -1; } /** * Recherche d'un motif avec l'algorithme de Knuth, Morris et Pratt. * @param pattern motif à rechercher * @param text texte dans lequel le motif est recherché * @return position de la première occurrence si le motif a au moins * une occurrence dans le texte et -1 sinon. */ static int knuthMorrisPratt(String pattern, String text) { int m = pattern.length();// Longueur du motif int n = text.length(); // Longueur du texte int[] r = new int[m]; // Fonction de suppléance int i; // Position dans le motif int j; // Position dans le texte // Calcul de la fonction de suppléance r // Pour tout i > 0, r[i] est la longueur du bord maximal compatible // du prefixe de longueur i du motif. Rappelons qu'un bord d'un // préfixe est compatible si son occurrence préfixe est suivie d'une // lettre différente de la lettre qui suit le préfixe. r[0] = i = -1; for (j = 1; j < m; j++) { // Ici i = s[j-1] while (i >= 0 && pattern.charAt(i) != pattern.charAt(j-1)) i = r[i]; i++; // Ici i = s[j] if (pattern.charAt(i) != pattern.charAt(j)) r[j] = i; else r[j] = r[i]; } // Recherche du motif i = 0; j = 0; while (i < m && j < n) { if (pattern.charAt(i) == text.charAt(j)) { // Si les deux caractères coïncident, // les deux curseurs avancent d'une position vers la droite. j++; i++; } else { // Version précédente // if (i == 0) // j++; // La nouvelle version prend en compte l'absence de bord // compatible c'est-à-dire le cas r[i] == -1 if (r[i] == -1) { i = 0; j++; } else i = r[i]; } } if (i == m) // Occurrence trouvée en position j-i return j-i; else // Aucune occurrence return -1; } public static void main(String [] args) { if (args.length > 1) { System.out.println(morrisPratt(args[0],args[1])); System.out.println(knuthMorrisPratt(args[0],args[1])); } else { System.out.println("Usage : java Pattern pattern text"); } } }