Rabin-Karpアルゴリズムを使用した文字列検索の効率的な実装方法

ハッシュ関数の選択: Rabin-Karpアルゴリズムでは、ハッシュ関数が重要な役割を果たします。ハッシュ関数は、文字列を数値に変換するために使用されます。一般的なハッシュ関数としては、単純な文字コードの和や乗算ハッシュなどがあります。
パターン文字列のハッシュ値の計算: パターン文字列のハッシュ値を計算します。これには、選択したハッシュ関数を使用します。
テキスト文字列内でのパターン文字列の検索: テキスト文字列内でのパターン文字列の検索を行います。まず、テキスト文字列の最初のパターン文字列の長さの部分文字列のハッシュ値を計算します。その後、ハッシュ値が一致する場合にのみ、実際に文字列の比較を行います。一致しない場合は、次の位置にスライドして再びハッシュ値を計算します。
パターン文字列が見つかった場合の処理: パターン文字列が見つかった場合には、該当する位置を記録するか、必要に応じて追加の処理を行います。

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

#include <iostream>
#include <string>
using namespace std;
// ハッシュ関数の実装例
int calculateHash(string str) {
    int hash = 0;
    for (char c : str) {
        hash += c;
    }
    return hash;
}
void searchPattern(string text, string pattern) {
    int patternHash = calculateHash(pattern);
    int patternLength = pattern.length();
    int textLength = text.length();
    for (int i = 0; i <= textLength - patternLength; i++) {
        string substring = text.substr(i, patternLength);
        int substringHash = calculateHash(substring);
        if (substringHash == patternHash && substring == pattern) {
            cout << "Pattern found at index " << i << endl;
        }
    }
}
int main() {
    string text = "This is a sample text";
    string pattern = "sample";
    searchPattern(text, pattern);
    return 0;
}

このコード例では、与えられたテキスト文字列内でパターン文字列を検索し、一致する位置を出力しています。ハッシュ関数としては、単純な文字コードの和を使用していますが、必要に応じて他のハッシュ関数を選択することもできます。

以上が、Rabin-Karpアルゴリズムを使用した文字列検索の効率的な実装方法とコード例です。これを参考にして、自身のプロジェクトやコーディング課題に応用してみてください。