Bagaimana untuk melaksanakan algoritma KMP menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma KMP

Algoritma KMP (algoritma Karp-Miller-Rosenberg) ialah algoritma pemadanan rentetan yang menggunakan maklumat yang telah dipadankan untuk mengelakkan pemadanan yang tidak perlu, dengan itu meningkatkan kecekapan pemadanan. Algoritma KMP ialah algoritma yang cekap apabila berurusan dengan padanan rentetan teks dan corak berskala besar. Artikel ini akan memperkenalkan cara menggunakan Java untuk melaksanakan algoritma KMP dan memberikan contoh kod khusus.

1. Prinsip algoritma KMP
1.1. Fungsi Awalan
Idea teras algoritma KMP adalah menggunakan fungsi awalan (juga dikenali sebagai awalan biasa dan akhiran) untuk mengendalikan lompatan rentetan corak apabila padanan gagal.

Fungsi awalan ialah pi tatasusunan, dengan pi[i] mewakili panjang awalan benar terpanjang dan akhiran benar terpanjang rentetan yang berakhir dengan aksara ke-i antara aksara i pertama rentetan corak. Sebagai contoh, fungsi awalan rentetan corak "ababaca" ialah [0, 0, 1, 2, 3, 0, 1].

1.2. Langkah utama algoritma KMP
Langkah utama algoritma KMP adalah seperti berikut:
1) Kira fungsi awalan rentetan corak
2) Padankan dalam rentetan teks dan gunakan fungsi awalan untuk mengendalikan situasi kegagalan sepadan.

2. Pelaksanaan algoritma KMP
Di bawah ini kami memperkenalkan cara menggunakan Java untuk melaksanakan algoritma 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");
        }
    }
}

Dalam kod di atas, fungsi computePrefixFunction digunakan untuk mengira fungsi awalan rentetan corak, dan fungsi carian digunakan untuk memadankan dalam rentetan teks. Dalam fungsi utama, kita boleh melihat cara memanggil fungsi carian untuk melaksanakan padanan corak dan mengeluarkan hasil padanan.

3. Ringkasan
Dengan menggunakan algoritma KMP, kami boleh melakukan operasi pemadanan rentetan dengan berkesan. Artikel ini memperkenalkan prinsip algoritma KMP dan cara menggunakan Java untuk melaksanakan algoritma KMP. Saya harap artikel ini akan membantu anda mempelajari dan memahami algoritma KMP.

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