close

(Text Search) C++ の テキスト検索アルゴリズム- 説明、例、コード

テキスト検索アルゴリズムは、テキスト処理と情報検索の基本的な方法です。 このアルゴリズムを使用すると、大きなテキスト内の部分文字列(またはパターン) の出現箇所を見つけて識別することができます。

使い方

  1. より大きなテキスト(またはドキュメント) と検索する部分文字列から始めます。
  2. テキストの各文字を順番に繰り返します。
  3. 部分文字列と、その部分文字列と同じ長さのテキストの一部を比較します。 一致するものが見つかった場合は、現在位置を記録します。
  4. 次の位置に移動して比較を続けます。

例

「アルゴリズムがどのように機能するかを確認するために、このテキスト内の部分文字列を検索してみましょう。」というテキストについて考えてみましょう。

検索する部分文字列: "substring"

  1. 位置 0 から開始します。 Let' 「部分文字列」と比較します。 勝ち目がない。
  2. 位置 1 に移動します。 et's 「部分文字列」と比較します。 勝ち目がない。
  3. 位置 2 に移動します。 t's 「」と「部分文字列」を比較します。一致しません。
  4. 位置 3 に移動します。 's s 「部分文字列」と比較します。 勝ち目がない。
  5. 位置 4 に移動します。 se 「部分文字列」と比較します。 勝ち目がない。
  6. 位置 5 に移動します。 sea 「部分文字列」と比較します。 勝ち目がない。
  7. 6 番目の位置に移動します。 earc 「部分文字列」と比較します。 勝ち目がない。
  8. 7 番目の位置に移動します。 arch 「部分文字列」と比較します。 勝ち目がない。
  9. 位置 8 に移動します。 rch 「」と「部分文字列」を比較します。一致しません。
  10. 9 番目の位置に移動します。 ch w 「部分文字列」と比較します。 勝ち目がない。
  11. 位置 10 に移動します。 h wi 「部分文字列」と比較します。 勝ち目がない。
  12. 位置 11 に移動します。「」 wit と「部分文字列」を比較します。一致しません。
  13. 位置 12 に移動します。 with 「部分文字列」と比較します。 勝ち目がない。
  14. 13 番目の位置に移動します。 ithi 「部分文字列」と比較します。 勝ち目がない。
  15. 位置 14 に移動します。 thin 「部分文字列」と比較します。 勝ち目がない。
  16. 15 番目の位置に移動します。 hinn 「部分文字列」と比較します。 勝ち目がない。
  17. 位置 16 に移動します。 in t 「部分文字列」と比較します。 勝ち目がない。
  18. 位置 17 に移動します。 n th 「部分文字列」と比較します。 勝ち目がない。
  19. 位置 18 に移動します。「」 thi と「部分文字列」を比較します。一致しません。
  20. 位置 19 に移動します。 this 「部分文字列」と比較します。 勝ち目がない。
  21. 位置 20 に移動します。 his 「」と「部分文字列」を比較します。一致しません。
  22. 位置 21 に移動します。 is t 「部分文字列」と比較します。 勝ち目がない。
  23. 位置 22 に移動します。 s te  「部分文字列」と比較します。 勝ち目がない。
  24. 位置 23 に移動します。 ubst  「部分文字列」と比較します。 勝ち目がない。
  25. 位置 24 に移動します。 bstr 「部分文字列」と比較します。 勝ち目がない。
  26. 位置 25 に移動します。 stre 「部分文字列」と比較します。 勝ち目がない。
  27. 位置 26 に移動します。 trin  「部分文字列」と比較します。 勝ち目がない。
  28. 位置 27 に移動します。 ring  「部分文字列」と比較します。 一致が見つかりました。レコード位置 27。

部分文字列「substring」はテキスト内の 27 番目の位置にあります。

C++ のコード例 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

この例では、この textSearch 関数を使用して、テキスト内の部分文字列「substring」の位置を検索します。 結果は、一致の開始位置を含むベクトルになります。