字符串匹配算法
字符串匹配（String Matching）是指在一个大的文本（主串）中查找一个较小的模式（子串）的位置或所有出现位置的问题。该问题通常要求找到子串在主串中出现的起始位置，或者在一些应用中可能需要找出所有匹配的子串。
暴力匹配算法（Brute Force）
算法基本思想：
- 从主串
str中pos位置起与子串sub中的第一个字符比较 - 若相等，则继续逐个比较后续字符
- 否则从主串
str的下一个字符起再重新比较 - 依次类推,直至子串
sub的每个字符和主串str中的一个连续的字符序列相等，则匹配成功，返回子串sub在主串str的起始下标 - 否则匹配失败，返回
-1
图例讲解
代码实现
int BruteForce(string str, string sub, int pos) {int i = pos;// 遍历主串int j = 0;// 遍历子串//当i小于主串长度且j小于子串长度时while (i < str.size() && j < sub.size()) {// 如果当前字符相等，则继续比较下一个字符if (str[i] == sub[j]) {i++;j++;}// 如果当前字符不相等，则i回退到上一个字符的下一个位置，j回退到0else {i = i - j + 1;j = 0;}}// 如果j等于子串长度，说明找到了子串if (j == sub.size()) {return i - j;}// 否则返回-1return -1;
}
时间复杂度
暴力匹配算法的时间复杂度是 O(n * m)，其中：
n是主串的长度。m是子串的长度。
为什么是 O(n * m)？
- 最坏情况：每次子串和主串的比较都需要
m次字符比较。而主串的长度是n，因此，最坏情况下需要比较n - m + 1次（即最多从主串的每个位置开始匹配一次）。每次匹配时，需要进行m次比较。因此，总的时间复杂度是O(n * m)。
