close

C++ の文字列検索 (String Search) アルゴリズム- 説明、例、コード

文字列検索アルゴリズムは、より大きなテキスト(文字列) 内で特定のパターン(部分文字列) の出現を見つけるために使用されます。 このアルゴリズムは、テキストの処理、検索、および操作のタスクにおいて重要な役割を果たします。

使い方

  1. 検索するテキスト(文字列) とパターン(部分文字列) から始めます。
  2. テキストを一度に 1 文字ずつ繰り返します。
  3. テキスト内の各文字について、パターンの最初の文字と比較します。
  4. 一致するものがあった場合は、後続の文字もパターンと一致するかどうかを確認します。
  5. パターンが完全に一致した場合は、一致の開始位置を記録します。
  6. テキスト内のパターンの検索を続けます。

例

テキスト:「ababcababcabcabc」とパターン:「abc」を考えてみましょう。

  1. 位置 0 から開始します。「a」をパターンの最初の文字「a」と比較します。
  2. 一致が見つかったら、次の文字に移動します。「b」と「b」、「a」と「c」。
  3. 「b」と「a」、「a」と「b」、「b」と「c」のマッチングを続けます。
  4. 位置 2 で試合が失敗しました。
  5. もう一度位置 3 から開始します。「a」をパターンの最初の文字「a」と比較します。
  6. 成功した一致: 「a」と「a」、「b」と「b」、「c」と「c」。
  7. 位置 3 を記録します。

パターン「abc」は位置 0、6、および 9 にあります。

C++ のコード例 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

この例では、この stringSearch 関数を使用して、テキスト「ababcababcabcabc」内でパターン「abc」が出現する箇所を検索します。 結果は、一致の開始位置を含むベクトルになります。