字符串匹配算法
字符串匹配(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)
。