Bagaimana untuk melaksanakan algoritma KMP dalam C#

Cara melaksanakan algoritma KMP dalam C#

Algoritma KMP (Knuth-Morris-Pratt) ialah algoritma pemadanan rentetan yang cekap digunakan untuk mencari kedudukan rentetan corak dalam rentetan teks. Idea terasnya ialah menggunakan maklumat separa yang telah dipadankan untuk mengelakkan perbandingan yang tidak perlu.

Kunci untuk melaksanakan algoritma KMP ialah membina jadual padanan separa (Jadual Padanan Separa), juga dipanggil tatasusunan seterusnya. Tatasusunan ini merekodkan panjang subrentetan akhiran padanan terpanjang untuk setiap subrentetan awalan dalam rentetan corak.

Berikut ialah langkah dan contoh kod khusus untuk melaksanakan algoritma KMP dalam C#:

Langkah 1: Bina jadual padanan separa

1. Tentukan tatasusunan integer bersebelahan dengan saiz panjang rentetan corak dan mulakan seterusnya[0] = -1 .
2. Tentukan dua penunjuk i dan j, masing-masing dengan nilai awal 0 dan -1.
3. Tentukan sama ada saya mencapai penghujung rentetan corak, jika tidak, lakukan langkah berikut:
   a Jika j bersamaan dengan -1 atau aksara semasa adalah sama dengan aksara yang sepadan dengan penunjuk j, maka i dan j adalah. bergerak ke belakang pada masa yang sama, dan seterusnya[i ] = j.
   b. Jika tidak, gerakkan penunjuk j ke kedudukan seterusnya[j] dan teruskan padanan.
4. Kembalikan jadual padanan separa yang dibina seterusnya.

Berikut ialah kod cara melaksanakan langkah di atas:

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

Langkah 2: Gunakan jadual padanan separa untuk memadankan

1. Tentukan dua penunjuk i dan j, menunjuk ke kedudukan permulaan rentetan dan corak teks rentetan masing-masing.
2. Tentukan sama ada i dan j telah sampai ke penghujung Jika tidak, lakukan langkah berikut:
   a. ke belakang pada masa yang sama.
   b. Jika tidak, gerakkan penunjuk j ke kedudukan seterusnya[j] dan teruskan padanan.
3. Jika penunjuk j menghala ke hujung rentetan corak, ia bermakna perlawanan berjaya dan indeks kedudukan permulaan dalam rentetan teks dikembalikan.
4. Jika perlawanan gagal, -1 akan dikembalikan.

Berikut ialah kod cara melaksanakan langkah di atas:

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

Dengan memanggil kaedah KMP dan menghantar rentetan teks dan rentetan corak, anda boleh mendapatkan hasil yang sepadan.

Di atas adalah langkah dan contoh kod tentang cara melaksanakan algoritma KMP dalam C#. Dengan menggunakan jadual padanan separa, algoritma KMP boleh meningkatkan kecekapan padanan rentetan dengan berkesan, terutamanya apabila memproses rentetan teks besar dan rentetan corak panjang, dengan prestasi yang lebih baik.

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