c++实现字符串匹配

常见的字符串匹配算法有暴力匹配、KMP算法、Boyer-Moore算法等。

暴力匹配算法思路比较简单，就是从文本串的第一个字符开始，依次与模式串的每个字符进行比较，如果每个字符都相同，则匹配成功；否则继续在文本串中向右移动一个字符，再进行比较，直到匹配成功或者文本串中没有足够的字符与模式串进行比较。

C++实现暴力匹配算法的代码如下：

#include <iostream>
#include <cstring>

using namespace std;

int brute_force(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            return i;
        }
    }
    return -1;
}

int main() {
    string text = "hello world";
    string pattern = "world";
    int pos = brute_force(text, pattern);
    if (pos == -1) {
        cout << "pattern not found" << endl;
    } else {
        cout << "pattern found at position " << pos << endl;
    }
    return 0;
}

这里使用了两个指针 `i` 和 `j` 分别指向文本串和模式串中正在比较的字符。如果当前字符匹配成功，则两个指针都向右移动一位，否则文本串指针向右移动一位，模式串指针回到开头重新开始匹配。

暴力匹配算法的时间复杂度为 $O(mn)$，其中 $m$ 是模式串长度，$n$ 是文本串长度。在最坏情况下，需要比较 $mn$ 次，因此当模式串比较长时，暴力匹配算法的效率会比较低。