close

(Text Search) C++ 中的 文本搜索算法- 解释、示例和代码

文本搜索算法是文本处理和信息检索的基本方法。 该算法允许我们定位和识别较大文本片段中子字符串（或模式）的出现。

怎么运行的

  1. 从较大的文本（或文档）和要搜索的子字符串开始。
  2. 按顺序迭代文本的每个字符。
  3. 将子字符串与与子字符串长度相同的文本部分进行比较。 如果找到匹配，则记录当前位置。
  4. 移动到下一个位置并继续比较。

例子

考虑以下文本：“让我们在该文本中搜索子字符串，看看算法是如何工作的。”

以及要搜索的子字符串：“substring”

  1. 从位置 0 开始。 Let' 与“substring”进行比较。 没有匹配。
  2. 移动到位置 1。 et's 与“substring”进行比较。 没有匹配。
  3. 移动到位置 2。将 t's " 与 "substring" 进行比较。没有匹配。
  4. 移动到位置 3。 's s 与“substring”进行比较。 没有匹配。
  5. 移动到位置 4。 se 与“substring”进行比较。 没有匹配。
  6. 移动到位置 5。 sea 与“substring”进行比较。 没有匹配。
  7. 移动到位置 6。 earc 与“substring”进行比较。 没有匹配。
  8. 移动到位置 7。 arch 与“substring”进行比较。 没有匹配。
  9. 移动到位置 8。将 rch " 与 "substring" 进行比较。没有匹配。
  10. 移动到位置 9。 ch w 与“substring”进行比较。 没有匹配。
  11. 移动到位置 10。 h wi 与“substring”进行比较。 没有匹配。
  12. 移动到位置 11。将 " wit 与 "substring" 进行比较。没有匹配。
  13. 移动到位置 12。 with 与“substring”进行比较。 没有匹配。
  14. 移动到位置 13。 ithi 与“substring”进行比较。 没有匹配。
  15. 移动到位置 14。 thin 与“substring”进行比较。 没有匹配。
  16. 移动到位置 15。 hinn 与“substring”进行比较。 没有匹配。
  17. 移动到位置 16。 in t 与“substring”进行比较。 没有匹配。
  18. 移动到位置 17。 n th 与“substring”进行比较。 没有匹配。
  19. 移动到位置 18。将 " thi 与 "substring" 进行比较。没有匹配。
  20. 移动到位置 19。 this 与“substring”进行比较。 没有匹配。
  21. 移动到位置 20。将 his " 与 "substring" 进行比较。没有匹配。
  22. 移动到位置 21。 is t 与“substring”进行比较。 没有匹配。
  23. 移动到位置 22。 s te  与“substring”进行比较。 没有匹配。
  24. 移动到位置 23。 ubst  与“substring”进行比较。 没有匹配。
  25. 移动到位置 24。 bstr 与“substring”进行比较。 没有匹配。
  26. 移动到位置 25。 stre 与“substring”进行比较。 没有匹配。
  27. 移动到位置 26。 trin  与“substring”进行比较。 没有匹配。
  28. 移动到位置 27。 ring  与“substring”进行比较。 找到匹配项，记录位置 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”在文本中的位置。 结果将是一个包含匹配起始位置的向量。