c++中如何实现字符串匹配_c++字符串匹配方法-C++-PHP中文网

c++中如何实现字符串匹配_c++字符串匹配方法

裘德小鎮的故事

发布： 2025-09-28 15:56:02

原创

741人浏览过

使用std::string::find进行字符串匹配，内置方法，简单高效，适合短文本查找，时间复杂度O(n*m)，未找到返回npos。

c++中如何实现字符串匹配_c++字符串匹配方法

在C++中实现字符串匹配有多种方式，从标准库函数到手动实现算法，可以根据需求选择合适的方法。以下是几种常用的字符串匹配方法，适合不同场景使用。

1. 使用 std::string::find 方法

std::string::find 是最简单直接的字符串匹配方式，适用于大多数基础查找场景。

特点：

内建于 std::string 类，无需额外实现
返回子串首次出现的位置，未找到返回 std::string::npos
时间复杂度约为 O(n*m)，适合短文本匹配

示例代码：

#include <string>
#include <iostream>

int main() {
    std::string text = "Hello, welcome to C++ world!";
    std::string pattern = "welcome";

    if (text.find(pattern) != std::string::npos) {
        std::cout     } else {
        std::cout     }
    return 0;
}

2. KMP 算法（Knuth-Morris-Pratt）

当需要高效匹配长文本或频繁搜索时，KMP 算法是更好的选择。它通过预处理模式串，避免回溯主串指针，实现 O(n + m) 的时间复杂度。

立即学习“C++免费学习笔记（深入）”；

核心思想：

构建“部分匹配表”（next 数组），记录模式串前缀与后缀的最长公共长度
利用该表跳过不必要的比较

示例实现：

#include <vector>
#include <string>

std::vector<int> buildNext(const std::string& pattern) {
    int n = pattern.size();
    std::vector<int> next(n, 0);
    int len = 0;
    int i = 1;

    while (i < n) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

bool kmpSearch(const std::string& text, const std::string& pattern) {
    int m = text.size(), n = pattern.size();
    if (n == 0) return true;
    if (m < n) return false;

std::vector<int> next = buildNext(pattern);
int i = 0, j = 0;

    while (i < m) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        if (j == n) {
            return true; // 找到匹配
            // 若需找所有位置，可记录 i-j 并 j = next[j-1];
        } else if (i < m && text[i] != pattern[j]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    return false;
}

3. 使用正则表达式（std::regex）

如果匹配规则较复杂（如模糊匹配、通配符、数字提取等），可以使用 C++11 提供的 std::regex。

标贝悦读AI配音

在线文字转语音软件-专业的配音网站

查看详情

适用场景：

邮箱、电话号码验证
格式化文本提取
支持 .*、\d、^、$ 等正则语法

示例：

#include <regex>
#include <string>
#include <iostream>

bool matchEmail(const std::string& email) {
std::regex pattern(R"(\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+.[A-Z|a-z]{2,}\b)");
return std::regex_search(email, pattern);
}