Comment implémenter un algorithme de correspondance de chaînes à l'aide de Java

Comment utiliser Java pour implémenter un algorithme de correspondance de chaînes

Introduction :
L'algorithme de correspondance de chaînes est un problème courant dans le domaine informatique, qui est utilisé pour trouver la position d'occurrence d'une chaîne de modèle spécifique dans une chaîne principale. Dans le développement réel, il est souvent nécessaire de faire correspondre des chaînes, comme la fonction de recherche dans les éditeurs de texte, la correspondance de mots clés dans les moteurs de recherche, etc. Cet article présentera plusieurs algorithmes courants de correspondance de chaînes et fournira des exemples de code Java correspondants.

1. Algorithme de correspondance par force brute
L'algorithme de correspondance par force brute, également connu sous le nom d'algorithme de correspondance naïf, est l'algorithme de correspondance de chaînes le plus basique. Son principe est très simple, c'est-à-dire qu'à partir de chaque position de la chaîne principale, il compare caractère par caractère avec la chaîne de modèle jusqu'à ce qu'un caractère ne correspondant pas apparaisse ou qu'une correspondance soit trouvée avec succès.

Le code d'implémentation spécifique est le suivant :

public class BruteForceMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

2. Algorithme KMP
L'algorithme KMP est un algorithme de correspondance de chaînes efficace. Il utilise des informations de correspondance partielle des chaînes de modèles pour éviter les comparaisons de caractères inutiles. Le cœur de l'algorithme KMP est de construire un tableau suivant pour enregistrer la longueur du suffixe commun le plus long à chaque position de la chaîne de modèle.

Le code d'implémentation spécifique est le suivant :

public class KMPMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == m) {
            return i - j;
        } else {
            return -1;
        }
    }

    private int[] getNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < m - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (pattern.charAt(i) != pattern.charAt(j)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

3. Algorithme de Boyer-Moore
L'algorithme de Boyer-Moore est un algorithme de correspondance de chaîne efficace qui utilise les informations de distribution de caractères et les règles de décalage vers l'arrière dans la chaîne de modèle.

Le code d'implémentation spécifique est le suivant :

public class BMMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] bmBc = preBmBc(pattern);
        int[] bmGs = preBmGs(pattern);
        int j = 0;
        while (j <= n - m) {
            int i;
            for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--);
            if (i < 0) {
                return j;
            } else {
                j += Math.max(bmGs[i], bmBc[text.charAt(i + j)] - m + 1 + i);
            }
        }
        return -1;
    }

    private int[] preBmBc(String pattern) {
        int[] bmBc = new int[256];
        int m = pattern.length();
        for (int i = 0; i < 256; i++) {
            bmBc[i] = m;
        }
        for (int i = 0; i < m - 1; i++) {
            bmBc[pattern.charAt(i)] = m - 1 - i;
        }
        return bmBc;
    }

    private int[] preBmGs(String pattern) {
        int m = pattern.length();
        int[] bmGs = new int[m];
        int i = m - 1, j = m;
        bmGs[m - 1] = m;
        while (i >= 0) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                bmGs[--i] = --j;
            } else {
                j = m - 1 - i;
                while (j < m && pattern.charAt(m - 1 - j) == pattern.charAt(j)) {
                    j++;
                }
                bmGs[i] = j;
            }
        }
        return bmGs;
    }
}

Conclusion :
Ce qui précède sont des exemples de code de trois algorithmes de correspondance de chaînes courants, qui sont l'algorithme de correspondance par force brute, l'algorithme KMP et l'algorithme de Boyer-Moore. Dans les applications pratiques, des algorithmes appropriés peuvent être sélectionnés en fonction de besoins spécifiques pour améliorer l'efficacité de la correspondance.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!