字符串匹配
本页面将简述字符串匹配问题以及它的解法。
字符串匹配问题¶
定义¶
又称模式匹配(pattern matching)。该问题可以概括为「给定字符串 \(S\) 和 \(T\),在主串 \(S\) 中寻找子串 \(T\)」。字符 \(T\) 称为模式串 (pattern)。
类型¶
- 单串匹配:给定一个模式串和一个待匹配串,找出前者在后者中的所有位置。
- 多串匹配:给定多个模式串和一个待匹配串,找出这些模式串在后者中的所有位置。
- 出现多个待匹配串时,将它们直接连起来便可作为一个待匹配串处理。
- 可以直接当做单串匹配,但是效率不够高。
- 其他类型:例如匹配一个串的任意后缀,匹配多个串的任意后缀……
暴力做法¶
简称 BF (Brute Force) 算法。该算法的基本思想是从主串 \(S\) 的第一个字符开始和模式串 \(T\) 的第一个字符进行比较,若相等,则继续比较二者的后续字符;否则,模式串 \(T\) 回退到第一个字符,重新和主串 \(S\) 的第二个字符进行比较。如此往复,直到 \(S\) 或 \(T\) 中所有字符比较完毕。
实现¶
/*
* s:待匹配的主串
* t:模式串
* n:主串的长度
* m:模式串的长度
*/
std::vector<int> match(char *s, char *t, int n, int m) {
std::vector<int> ans;
int i, j;
for (i = 0; i < n - m + 1; i++) {
for (j = 0; j < m; j++) {
if (s[i + j] != t[j]) break;
}
if (j == m) ans.push_back(i);
}
return ans;
}
def match(s, t, n, m):
if m < 1:
return []
ans = []
for i in range(0, n - m + 1):
for j in range(0, m):
if s[i + j] != t[j]:
break
else:
ans.append(i)
return ans
时间复杂度¶
设 \(n\) 为主串的长度,\(m\) 为模式串的长度。默认 \(m\ll n\)。
在最好情况下,BF 算法匹配成功时,时间复杂度为 \(O(n)\);匹配失败时,时间复杂度为 \(O(m)\)。
在最坏情况下,每趟不成功的匹配都发生在模式串的最后一个字符,BF 算法要执行 \(m(n-m+1)\) 次比较,时间复杂度为 \(O(nm)\)。
如果模式串有至少两个不同的字符,则 BF 算法的平均时间复杂度为 \(O(n)\)。但是在 OI 题目中,给出的字符串一般都不是纯随机的。
Hash 的方法¶
参见:字符串哈希
KMP 算法¶
参见:前缀函数与 KMP 算法