C++でのKMPアルゴリズムの実装と使用方法

まず、KMPアルゴリズムの基本的なアイデアを説明しましょう。通常の文字列検索アルゴリズムでは、パターン文字列とテキスト文字列を一致させながら進めていきますが、一致しない場合には一致位置をバックトラックする必要があります。KMPアルゴリズムでは、パターン文字列内の一部分について、一致しなかった場合にどれだけ一致位置をスキップするかを事前に計算しておくことで、効率的な検索が可能となります。

以下に、シンプルで簡単なC++のKMPアルゴリズムの実装例を示します。

#include <iostream>
#include <vector>
using namespace std;
vector<int> computeLPSArray(const string& pattern) {
    int n = pattern.length();
    vector<int> lps(n, 0);
    int len = 0;
    int i = 1;

    while (i < n) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}
vector<int> KMP(const string& text, const string& pattern) {
    vector<int> lps = computeLPSArray(pattern);
    vector<int> indices;
    int m = pattern.length();
    int n = text.length();
    int i = 0;
    int j = 0;

    while (i < n) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == m) {
            indices.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    return indices;
}
int main() {
    string text = "This is a sample text for testing the KMP algorithm.";
    string pattern = "sample";

    vector<int> indices = KMP(text, pattern);

    if (indices.empty()) {
        cout << "Pattern not found in the text." << endl;
    } else {
        cout << "Pattern found at indices: ";
        for (int index : indices) {
            cout << index << " ";
        }
        cout << endl;
    }

    return 0;
}

上記のコードでは、まずcomputeLPSArray関数で、パターン文字列の一致位置をスキップするためのLPS（Longest Proper Prefix which is also Suffix）配列を計算しています。次に、KMP関数でテキスト文字列とパターン文字列を比較しながら一致位置を検索し、一致した場所のインデックスをindicesベクターに格納しています。最後に、結果を表示しています。

このコードを実行すると、指定したパターンがテキスト内で見つかる場合には、"Pattern found at indices: "というメッセージと、一致した位置のインデックスが表示されます。もしパターンが見つからない場合には、"Pattern not found in the text."というメッセージが表示されます。

以上が、C++でのKMPアルゴリズムの簡単な実装と使用方法についての説明です。このアルゴリズムを使うことで、効率的な文字列検索や文字列マッチングが可能となります。