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

まず、KMPアルゴリズムの基本的なアイデアについて説明します。KMPアルゴリズムは、パターン文字列内の文字の比較を最小限に抑えることで、効率的な文字列検索を実現します。このアルゴリズムでは、パターン文字列内の部分文字列のマッチング情報を事前に計算し、その情報を利用して文字列の検索を行います。

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

#include <iostream>
#include <vector>
using namespace std;
vector<int> computeLPS(string pattern) {
    int patternLength = pattern.length();
    vector<int> lps(patternLength, 0);
    int len = 0;
    int i = 1;
    while (i < patternLength) {
        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;
}
void KMPSearch(string text, string pattern) {
    int textLength = text.length();
    int patternLength = pattern.length();
    vector<int> lps = computeLPS(pattern);
    int i = 0;
    int j = 0;
    while (i < textLength) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == patternLength) {
            cout << "パターンが見つかりました。インデックス: " << i - j << endl;
            j = lps[j - 1];
        } else if (i < textLength && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}
int main() {
    string text = "これはテスト用のテキストです。";
    string pattern = "テスト";
    KMPSearch(text, pattern);
    return 0;
}

上記のコードでは、computeLPS関数はパターン文字列の最長共通接頭辞（Longest Proper Prefix that is also Suffix, LPS）を計算し、KMPSearch関数は与えられたテキスト文字列内でパターン文字列を検索します。KMPSearch関数を呼び出すことで、パターンが見つかった場合にそのインデックスを表示します。

この例では、テキスト文字列として「これはテスト用のテキストです。」を使用し、パターン文字列として「テスト」を使用しています。実行すると、パターンが見つかった場合にそのインデックスが出力されます。

KMPアルゴリズムは、文字列検索の効率的な実装手法の一つです。他の言語でも同様の実装が可能ですが、上記のC++の例を参考にすることで基本的な考え方を理解することができます。