Algoritma pemadanan rentetan dan pelaksanaannya dalam C++

Dalam pengaturcaraan C++, masalah padanan rentetan adalah sangat biasa. Ringkasnya, masalah padanan rentetan ialah proses mencari rentetan corak tertentu dalam rentetan teks. Dalam aplikasi praktikal, algoritma pemadanan rentetan digunakan terutamanya dalam bidang seperti carian teks, pengecaman imej dan pemprosesan bahasa semula jadi. Artikel ini akan menumpukan pada algoritma pemadanan rentetan yang biasa digunakan dan pelaksanaannya dalam C++.

1. Algoritma pemadanan rentetan naif

Algoritma pemadanan rentetan naif juga dipanggil algoritma pemadanan carian brute force. Ideanya adalah untuk cuba memadankan rentetan corak P secara berturut-turut pada setiap kedudukan rentetan teks T sehingga kedudukan yang sepadan ditemui atau P tidak wujud dalam keseluruhan T. Kerumitan masa algoritma ini adalah tinggi, O(n*m), di mana n dan m ialah panjang rentetan teks T dan rentetan corak P masing-masing.

Kod C++ dilaksanakan seperti berikut:

void naive_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    for(int i = 0; i <= n-m; i++) {
        int j;
        for(j = 0; j < m; j++) {
            if(T[i+j] != P[j]) break;
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i << endl;
        }
    }
}

2. Algoritma pemadanan rentetan KMP

Algoritma pemadanan rentetan KMP ialah algoritma pemadanan rentetan klasik dan akhiran digunakan untuk padanan untuk mengelakkan padanan berulang bagi aksara yang telah dipadankan dalam rentetan teks T. Kerumitan masa algoritma ini ialah O(n), dengan n ialah panjang rentetan teks.

Kod C++ dilaksanakan seperti berikut:

void get_next(string P, vector<int>& next) {
    int m = P.length();
    next[0] = -1;
    int i = 0;
    int j = -1;
    while(i < m) {
        if(j == -1 || P[i] == P[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void kmp_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> next(m+1);
    get_next(P, next);
    int i = 0;
    int j = 0;
    while(i < n) {
        if(j == -1 || T[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i-m << endl;
            j = next[j];
        }
    }
}

3. Algoritma pemadanan rentetan BM

Algoritma BM ialah algoritma pemadanan rentetan berdasarkan watak buruk dan peraturan akhiran yang baik. Idea terasnya adalah untuk melangkau aksara yang dipadankan dengan memadankan aksara terakhir rentetan corak P dan pramemproses aksara yang tidak sepadan dalam rentetan teks T. Kerumitan masa bagi algoritma ini ialah O(n).

Kod C++ dilaksanakan seperti berikut:

const int MAXCHAR = 256;

void bm_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> badchar(MAXCHAR, -1);
    for(int i = 0; i < m; i++) {
        badchar[int(P[i])] = i;
    }
    vector<int> suffix(m+1);
    vector<bool> prefix(m+1);
    get_suffix_prefix(P, suffix, prefix);
    int i = 0;
    while(i <= n-m) {
        int j = m-1;
        while(j >= 0 && P[j] == T[i+j]) j--;
        if(j < 0) {
            cout << "Pattern occurs with shift " << i << endl;
            i += (i+m < n) ? m-badchar[int(T[i+m])] : 1;
        } else {
            i += max(suffix[j+1], j-badchar[int(T[i+j])]);
        }
    }
}

Artikel ini terutamanya memperkenalkan algoritma pemadanan rentetan yang biasa digunakan dan pelaksanaannya dalam C++. Walaupun algoritma pemadanan rentetan naif adalah mudah, kerumitan masanya adalah tinggi, manakala algoritma KMP dan BM boleh mencari kedudukan padanan dengan lebih cepat. Antaranya, algoritma KMP sesuai untuk rentetan corak pendek, dan algoritma BM sesuai untuk rentetan corak panjang. Dalam aplikasi sebenar, kita perlu memilih algoritma yang sesuai untuk pemadanan rentetan mengikut situasi yang berbeza.

Atas ialah kandungan terperinci Algoritma pemadanan rentetan dan pelaksanaannya dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!