字符串匹配
本页面将简述字符串匹配问题以及它的解法。
字符串匹配问题
定义
又称模式匹配(pattern matching)。该问题可以概括为「给定字符串
类型
- 单串匹配:给定一个模式串和一个待匹配串,找出前者在后者中的所有位置。
- 多串匹配:给定多个模式串和一个待匹配串,找出这些模式串在后者中的所有位置。
- 出现多个待匹配串时,将它们直接连起来便可作为一个待匹配串处理。
- 可以直接当做单串匹配,但是效率不够高。
- 其他类型:例如匹配一个串的任意后缀,匹配多个串的任意后缀……
暴力做法
简称 BF (Brute Force) 算法。该算法的基本思想是从主串
实现
时间复杂度
设
BF 算法匹配成功时,在最好情况下,只有一趟匹配成功,此趟比较次数为
BF 算法匹配失败时,在最好情况下,每趟不成功的匹配都发生在模式串的第一个字符,BF 算法要执行
如果模式串有至少两个不同的字符,则 BF 算法的平均时间复杂度为
Hash 的方法
参见:字符串哈希
KMP 算法
参见:前缀函数与 KMP 算法
最后更新: 2023年11月21日
创建日期: 2018年8月6日
创建日期: 2018年8月6日