Bagaimana untuk melaksanakan algoritma Boyer-Moore menggunakan java

Cara melaksanakan algoritma Boyer-Moore menggunakan Java

Pengenalan:
Dalam sains komputer, pemadanan rentetan adalah tugas biasa. Algoritma padanan rentetan adalah kunci untuk menyelesaikan masalah ini. Salah satu algoritma pemadanan rentetan yang cekap ialah algoritma Boyer-Moore. Artikel ini akan memperkenalkan cara menggunakan bahasa Java untuk melaksanakan algoritma ini dan melampirkan contoh kod tertentu.

Prinsip algoritma Boyer-Moore:
Algoritma Boyer-Moore ialah algoritma pemadanan rentetan berbilang corak Ia memproses rentetan corak dan menggabungkan peraturan akhiran yang baik dan peraturan watak yang buruk . Idea teras adalah untuk melangkau aksara yang tidak dapat dipadankan sebanyak mungkin semasa proses pemadanan antara rentetan corak dan rentetan yang akan dipadankan, dengan itu meningkatkan kecekapan pemadanan.

Langkah pelaksanaan khusus:

1. Prapemprosesan rentetan corak:
   Pertama, kita perlu praproses rentetan corak: dan menjana dua Array rentetan tatasusunan aksara buruk dan tatasusunan akhiran yang baik.

   • Susun atur aksara buruk: menyimpan kedudukan paling kanan setiap aksara dalam rentetan corak.
   • Susun atur akhiran yang baik: rekod kedudukan kejadian paling kanan subrentetan akhiran rentetan corak dalam rentetan corak dan rekod sama ada subrentetan ini sepadan dengan awalan rentetan corak.

2. Proses pemadanan:
   Semasa proses pemadanan, kita mula memadankan ke hadapan dari hujung rentetan untuk dipadankan.

   • Pertama, selaraskan hujung rentetan corak dengan hujung rentetan yang hendak dipadankan, dan cuba padankan.
   • Jika perlawanan berjaya, kedudukan permulaan perlawanan dikembalikan, jika tidak kedudukan rentetan corak digerakkan mengikut watak buruk dan peraturan akhiran yang baik untuk meneruskan pemadanan.

Kod khusus adalah seperti berikut:

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");
        }
    }
}

Ringkasan:
Artikel ini memperkenalkan cara menggunakan bahasa Java untuk melaksanakan algoritma Boyer- Moore, dan menunjukkan penggunaan algoritma melalui contoh kod tertentu. Algoritma Boyer-Moore mempunyai kecekapan tinggi dan aplikasi yang luas dalam bidang padanan rentetan Dengan menggunakan secara rasional peraturan perwatakan yang baik dan buruk, kecekapan pemadanan rentetan boleh dipertingkatkan dengan lebih baik. Saya harap artikel ini akan membantu anda memahami dan mempraktikkan algoritma Boyer-Moore.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma Boyer-Moore menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!