文字列一致アルゴリズムとその C++ での実装

C プログラミングでは、文字列一致の問題が非常によく発生します。簡単に言えば、文字列マッチング問題は、テキスト文字列内の特定のパターン文字列を見つけるプロセスです。実際のアプリケーションでは、文字列マッチング アルゴリズムは主にテキスト検索、画像認識、自然言語処理などの分野で使用されます。この記事では、一般的に使用される文字列一致アルゴリズムとその C での実装に焦点を当てます。

1. 単純な文字列一致アルゴリズム

単純な文字列一致アルゴリズムは、ブルート フォース検索一致アルゴリズムとも呼ばれます。この考え方は、一致する位置が見つかるか、T 全体に P が存在しなくなるまで、テキスト文字列 T の各位置でパターン文字列 P との一致を連続的に試行することです。このアルゴリズムの時間計算量は O(n*m) と高く、n と m はそれぞれテキスト文字列 T とパターン文字列 P の長さです。

C コードの実装は次のとおりです:

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. KMP 文字列マッチング アルゴリズム

KMP 文字列マッチング アルゴリズムは、古典的な文字列マッチング アルゴリズムです。パターン文字列 P の最も長い共通の接頭辞と接尾辞を照合することで、テキスト文字列 T 内のすでに一致した文字の繰り返しの照合を避けることです。このアルゴリズムの時間計算量は O(n) です。ここで、n はテキスト文字列の長さです。

C コードの実装は次のとおりです。

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. BM 文字列マッチング アルゴリズム

BM アルゴリズムは、不正な文字と適切なサフィックス ルールのマッチングに基づく文字列です。アルゴリズム。その中心的な考え方は、パターン文字列 P の最後の文字を一致させ、テキスト文字列 T 内の一致しない文字を前処理することによって、一致した文字をスキップすることです。このアルゴリズムの時間計算量は O(n) です。

C コードは次のように実装されます。

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

この記事では主に、C で一般的に使用される文字列一致アルゴリズムとその実装について紹介します。単純な文字列マッチング アルゴリズムはシンプルですが、時間計算量が高くなります。一方、KMP アルゴリズムと BM アルゴリズムは、より迅速にマッチング位置を見つけることができます。このうち、KMP アルゴリズムは短いパターン列に適しており、BM アルゴリズムは長いパターン列に適しています。実際のアプリケーションでは、さまざまな状況に応じて文字列マッチングに適切なアルゴリズムを選択する必要があります。

以上が文字列一致アルゴリズムとその C++ での実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。