C++蛮力字符串匹配

蛮力字符串匹配算法（Brute-Force String Matching Algorithm）是一种简单粗暴却常用的字符串匹配算法。C++实现如下：

#include <iostream>
#include <string>

using namespace std;

int bruteForceSearch(string T, string P) {
    int n = T.length(); // 主串长度
    int m = P.length(); // 模式串长度
    for (int i = 0; i <= n - m; i++) { // 枚举主串中所有可能出现模式串的起始位置
        int j = 0;
        while (j < m && T[i+j] == P[j]) { // 模式串和主串中对应位置依次比较
            j++;
        }
        if (j == m) { // 如果完全匹配，返回模式串在主串中的位置
            return i;
        }
    }
    return -1; // 如果匹配失败，返回-1
}

int main() {
    string T = "ababcabcacbab";
    string P = "abcac";
    int pos = bruteForceSearch(T, P);
    if (pos != -1) {
        cout << "模式串在主串中的位置是：" << pos << endl;
    } else {
        cout << "模式串不在主串中出现！" << endl;
    }
    return 0;
}

该算法的时间复杂度为 $O(nm)$，其中 $n$ 是主串的长度，$m$ 是模式串的长度。在最坏情况下，需要比较 $n-m+1$ 次，即主串中每个长度为 $m$ 的子串都要和模式串进行比较，因此时间复杂度为 $O(nm)$。