C++实现文本字符串模式搜索：匹配b数量可变的abc模式

需求拆解 #

你需要匹配的子串规则等价于：以a开头，后跟至少1个连续的b，最后以c结尾，正则形式可表示为ab+c。

方案1：朴素遍历实现（适合短文本） #

思路：逐个遍历字符定位起始a，向后统计连续b的数量，确认后续字符为c时提取匹配子串。
代码实现：

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> matchPattern(const std::string& s) {
    std::vector<std::string> matches;
    int len = s.size();
    for (int i = 0; i < len; ++i) {
        // 定位起始字符a
        if (s[i] != 'a') continue;
        int pos = i + 1;
        // 统计连续b的数量
        while (pos < len && s[pos] == 'b') {
            pos++;
        }
        // 满足至少1个b且后续字符为c
        if (pos > i + 1 && pos < len && s[pos] == 'c') {
            matches.push_back(s.substr(i, pos - i + 1));
            // 若允许匹配重叠子串，可删除下行i=pos的赋值
            i = pos;
        }
    }
    return matches;
}

int main() {
    std::string input = "abaxavabaabcabbc";
    auto res = matchPattern(input);
    for (const auto& str : res) {
        std::cout << str << std::endl;
    }
    return 0;
}

方案2：有限状态机实现（适合长文本，O(n)时间复杂度） #

思路：通过状态流转单次遍历字符串，无需回溯，性能更高：

• 状态0：寻找起始字符a
• 状态1：寻找连续的b
• 匹配到非b字符时校验是否为结尾c，符合规则则记录结果
  代码实现：

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> matchPatternFSM(const std::string& s) {
    std::vector<std::string> matches;
    enum State { FIND_A, FIND_B };
    State curState = FIND_A;
    int startIdx = 0;

    for (int i = 0; i < s.size(); ++i) {
        switch (curState) {
            case FIND_A:
                if (s[i] == 'a') {
                    startIdx = i;
                    curState = FIND_B;
                }
                break;
            case FIND_B:
                if (s[i] != 'b') {
                    if (s[i] == 'c' && i > startIdx + 1) {
                        matches.push_back(s.substr(startIdx, i - startIdx + 1));
                    }
                    curState = FIND_A;
                    // 当前字符为a时直接进入下一轮匹配，避免漏判
                    if (s[i] == 'a') {
                        startIdx = i;
                        curState = FIND_B;
                    }
                }
                break;
        }
    }
    return matches;
}

int main() {
    std::string input = "abaxavabaabcabbc";
    auto res = matchPatternFSM(input);
    for (const auto& str : res) {
        std::cout << str << std::endl;
    }
    return 0;
}

输出结果 #

两种方案的运行输出均为：

abc
abbc

内容的提问来源于stack exchange，提问作者Psh programmer