Comment implémenter l'algorithme KMP en utilisant Java

Comment utiliser Java pour implémenter l'algorithme KMP

L'algorithme KMP (algorithme de Karp-Miller-Rosenberg) est un algorithme de correspondance de chaînes qui utilise des informations déjà correspondantes pour éviter les correspondances inutiles, améliorant ainsi l'efficacité de la correspondance. L'algorithme KMP est un algorithme efficace pour traiter des correspondances de texte et de chaînes de modèles à grande échelle. Cet article explique comment utiliser Java pour implémenter l'algorithme KMP et donne des exemples de code spécifiques.

1. Principe de l'algorithme KMP
1.1. Fonction préfixe
L'idée principale de l'algorithme KMP est d'utiliser la fonction préfixe (également connue sous le nom de préfixe et suffixe commun le plus long) pour gérer le saut de la chaîne de modèle lorsque le la correspondance échoue.

La fonction préfixe est un tableau pi, où pi[i] représente la longueur du vrai préfixe le plus long et du vrai suffixe le plus long de la chaîne se terminant par le i-ème caractère parmi les i premiers caractères de la chaîne de modèle. Par exemple, la fonction préfixe de la chaîne de modèle « ababaca » est [0, 0, 1, 2, 3, 0, 1].

1.2. Principales étapes de l'algorithme KMP
Les principales étapes de l'algorithme KMP sont les suivantes :
1) Calculer la fonction préfixe de la chaîne de modèle
2) Faire correspondre la chaîne de texte et utiliser la fonction préfixe pour gérer la situation de échec de correspondance.

2. Implémentation de l'algorithme KMP
Ci-dessous, nous présentons comment utiliser Java pour implémenter l'algorithme KMP.

public class KMP {
    public static int[] computePrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int k = 0;
        for (int i = 1; i < m; i++) {
            while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
                k = pi[k - 1];
            }
            if (pattern.charAt(k) == pattern.charAt(i)) {
                k++;
            }
            pi[i] = k;
        }
        return pi;
    }

    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] pi = computePrefixFunction(pattern);
        int q = 0;
        for (int i = 0; i < n; i++) {
            while (q > 0 && pattern.charAt(q) != text.charAt(i)) {
                q = pi[q - 1];
            }
            if (pattern.charAt(q) == text.charAt(i)) {
                q++;
            }
            if (q == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "ababababacaba";
        String pattern = "bac";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

Dans le code ci-dessus, la fonction calculatePrefixFunction est utilisée pour calculer la fonction préfixe de la chaîne de modèle, et la fonction de recherche est utilisée pour faire correspondre la chaîne de texte. Dans la fonction principale, nous pouvons voir comment appeler la fonction de recherche pour effectuer une correspondance de modèles et afficher les résultats de la correspondance.

3. Résumé
En utilisant l'algorithme KMP, nous pouvons effectuer efficacement des opérations de correspondance de chaînes. Cet article présente le principe de l'algorithme KMP et comment utiliser Java pour implémenter l'algorithme KMP. J'espère que cet article vous aidera à apprendre et à comprendre l'algorithme KMP.

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!