Bagaimana untuk melaksanakan algoritma pemadanan rentetan menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma pemadanan rentetan

Pengenalan:
Algoritma pemadanan rentetan adalah masalah biasa dalam medan komputer , digunakan untuk mencari kedudukan kejadian rentetan corak tertentu dalam rentetan utama. Dalam pembangunan sebenar, selalunya perlu untuk memadankan rentetan, seperti fungsi carian dalam editor teks, padanan kata kunci dalam enjin carian, dsb. Artikel ini akan memperkenalkan beberapa algoritma padanan rentetan biasa dan menyediakan contoh kod Java yang sepadan.

1. Algoritma pemadanan ganas
Algoritma pemadanan ganas, juga dikenali sebagai algoritma pemadanan naif, ialah algoritma pemadanan rentetan yang paling asas. Prinsipnya sangat mudah, iaitu, bermula dari setiap kedudukan dalam rentetan utama, ia membandingkan watak demi watak dengan rentetan corak sehingga watak tidak sepadan muncul atau padanan berjaya ditemui.

Kod pelaksanaan khusus adalah seperti berikut:

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. Algoritma KMP
Algoritma KMP ialah algoritma pemadanan rentetan yang cekap yang menggunakan padanan separa maklumat rentetan corak, mengelakkan perbandingan watak yang tidak perlu. Teras algoritma KMP adalah untuk membina tatasusunan seterusnya untuk merekodkan panjang akhiran biasa terpanjang pada setiap kedudukan dalam rentetan corak.

Kod pelaksanaan khusus adalah seperti berikut:

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 Algoritma Boyer-Moore
Algoritma Boyer-Moore ialah algoritma pemadanan rentetan yang cekap yang menggunakan rentetan corak Aksara. maklumat pengedaran dan peraturan anjakan belakang dalam .

Kod pelaksanaan khusus adalah seperti berikut:

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

Kesimpulan:
Di atas adalah contoh kod bagi tiga algoritma pemadanan rentetan biasa, ia adalah algoritma pemadanan kuasa kasar, Algoritma KMP dan algoritma Boyer-Moore. Dalam aplikasi praktikal, algoritma yang sesuai boleh dipilih mengikut keperluan khusus untuk meningkatkan kecekapan pemadanan.

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