close

C++ 中的字符串搜索 (String Search) 算法- 说明、示例和代码

字符串搜索算法用于查找较大文本（字符串）中特定模式（子字符串）的出现。 该算法在文本处理、搜索和操作任务中发挥着至关重要的作用。

怎么运行的

  1. 从要搜索的文本（字符串）和模式（子字符串）开始。
  2. 一次一个字符地遍历文本。
  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”的出现情况。 结果将是一个包含匹配起始位置的向量。