Comment implémenter l'algorithme de Boyer-Moore en utilisant Java

Comment implémenter l'algorithme de Boyer-Moore à l'aide de Java

Introduction :
En informatique, la correspondance de chaînes est une tâche courante. L’algorithme de correspondance de chaînes est la clé pour résoudre ce problème. L'algorithme de Boyer-Moore est l'un des algorithmes efficaces de correspondance de chaînes. Cet article expliquera comment utiliser le langage Java pour implémenter cet algorithme et joindra des exemples de code spécifiques.

Principe de l'algorithme de Boyer-Moore :
L'algorithme de Boyer-Moore est un algorithme de correspondance de chaînes multi-modèles. Il complète la correspondance en prétraitant la chaîne de modèle et en combinant les bonnes règles de suffixe et les mauvaises règles de caractères. L'idée principale est d'ignorer autant que possible les caractères sans correspondance pendant le processus de correspondance entre la chaîne de modèle et la chaîne à mettre en correspondance, améliorant ainsi l'efficacité de la correspondance.

Étapes spécifiques de mise en œuvre :

1. Prétraitement de la chaîne de modèle :
   Tout d'abord, nous devons prétraiter la chaîne de modèle et générer deux tableaux : un mauvais tableau de caractères et un bon tableau de suffixes.

   • Tableau de caractères incorrect : stocke la position d'occurrence la plus à droite de chaque caractère dans la chaîne de modèle.
   • Bon tableau de suffixes : enregistrez la position d'occurrence la plus à droite de la sous-chaîne de suffixe de la chaîne de modèle dans la chaîne de modèle et enregistrez si cette sous-chaîne correspond au préfixe de la chaîne de modèle.

2. Processus de correspondance :
   Pendant le processus de correspondance, nous commençons la correspondance en avant à partir de la fin de la chaîne à mettre en correspondance.

   • Tout d'abord, alignez l'extrémité de la chaîne du motif avec l'extrémité de la chaîne à faire correspondre et essayez de faire correspondre.
   • Si la correspondance réussit, la position de départ de la correspondance est renvoyée, sinon la position de la chaîne de motif est déplacée selon les règles de mauvais caractère et de bon suffixe pour continuer la correspondance.

Le code spécifique est le suivant :

import java.util.Arrays;

public class BoyerMoore {

    private static final int NO_OF_CHARS = 256;

    private int[] badCharShift;
    private int[] suffixShift;
    private boolean[] goodSuffix;

    public void preProcessPattern(String pattern) {
        int m = pattern.length();
        // 初始化数组
        badCharShift = new int[NO_OF_CHARS];
        suffixShift = new int[m + 1];
        goodSuffix = new boolean[m + 1];

        Arrays.fill(badCharShift, -1);
        for (int i = 0; i < m; i++) {
            badCharShift[pattern.charAt(i)] = i;
        }

        int f = 0;
        int g = 0;
        suffixShift[m] = m + 1;

        for (int i = m - 1; i >= 0; i--) {
            if (i > f && suffixShift[i + m - f] < i - f) {
                suffixShift[i] = suffixShift[i + m - f];
            } else {
                if (i < f) {
                    f = i;
                }
                g = i;
                while (f >= 0 && pattern.charAt(f) == pattern.charAt(f + m - g)) {
                    f--;
                }
                suffixShift[i] = g - f;
            }
        }

        for (int i = 0; i < m; i++) {
            goodSuffix[i] = suffixShift[i] > m - i;
        }
    }

    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int i = 0;

        while (i <= n - m) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }
            if (j < 0) {
                return i; // 匹配成功，返回匹配位置
            } else {
                i += Math.max(goodSuffix[j + 1], j - badCharShift[text.charAt(i + j)]);
            }
        }
        return -1; // 未匹配成功，返回-1
    }

    public static void main(String[] args) {
        BoyerMoore bm = new BoyerMoore();
        String text = "This is a test";
        String pattern = "test";
        bm.preProcessPattern(pattern);
        int index = bm.search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

Résumé :
Cet article présente comment utiliser le langage Java pour implémenter l'algorithme de Boyer-Moore et démontre l'utilisation de l'algorithme à travers des exemples de code spécifiques. L'algorithme de Boyer-Moore présente une grande efficacité et une large application dans le domaine de la correspondance de chaînes. En utilisant rationnellement les bonnes règles de suffixe et de mauvais caractères, l'efficacité de la correspondance de chaînes peut être considérablement améliorée. J'espère que cet article vous aidera à comprendre et à mettre en pratique l'algorithme de Boyer-Moore.

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!