字符串匹配
本页面将简述字符串匹配问题以及它的解法．
字符串匹配问题
定义
又称模式匹配（pattern matching）．该问题可以概括为「给定字符串 𝑆S
和 𝑇T，在主串 𝑆S 中寻找子串 𝑇T」．字符 𝑇T 称为模式串 (pattern)．
类型
- 单串匹配：给定一个模式串和一个待匹配串，找出前者在后者中的所有位置．
- 多串匹配：给定多个模式串和一个待匹配串，找出这些模式串在后者中的所有位置．
- 出现多个待匹配串时，将它们直接连起来便可作为一个待匹配串处理．
- 可以直接当做单串匹配，但是效率不够高．
- 其他类型：例如匹配一个串的任意后缀，匹配多个串的任意后缀……
暴力做法
简称 BF (Brute Force) 算法．该算法的基本思想是从主串 𝑆S 的第一个字符开始和模式串 𝑇T 的第一个字符进行比较，若相等，则继续比较二者的后续字符；否则，模式串 𝑇T 回退到第一个字符，重新和主串 𝑆S 的第二个字符进行比较．如此往复，直到 𝑆S 或 𝑇T 中所有字符比较完毕．
实现
C++Python
---|---
---|---
时间复杂度
设 𝑛n 为主串的长度，𝑚m 为模式串的长度．默认 𝑚 ≪𝑛m≪n．
BF 算法匹配成功时，在最好情况下，只有一趟匹配成功，此趟比较次数为 𝑚m，而其余每趟不成功的匹配都发生在模式串的第一个字符，还需要 𝑛 −𝑚n−m 次比较，总比较次数为 𝑛n，故时间复杂度为 𝑂(𝑛)O(n)；在最坏情况下，匹配成功的趟数为 𝑛 −𝑚 +1n−m+1，每趟比较次数为 𝑚m，总比较次数为 𝑚(𝑛 −𝑚 +1)m(n−m+1)，故时间复杂度为 𝑂(𝑚𝑛)O(mn)．
BF 算法匹配失败时，在最好情况下，每趟不成功的匹配都发生在模式串的第一个字符，BF 算法要执行 𝑛 −𝑚 +1n−m+1 次比较，时间复杂度为 𝑂(𝑛)O(n)；在最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符，BF 算法要执行 𝑚(𝑛 −𝑚 +1)m(n−m+1) 次比较，时间复杂度为 𝑂(𝑚𝑛)O(mn)．
如果模式串有至少两个不同的字符，则 BF 算法的平均时间复杂度为 𝑂(𝑛)O(n)．但是在 OI 题目中，给出的字符串一般都不是纯随机的．
Hash 的方法
参见：字符串哈希
KMP 算法
参见：前缀函数与 KMP 算法
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Xeonacid, Enter-tainer, iamtwz, ksyx, abc1763613206, f1rstmehul, HeRaNO, karman011, Menci, NachtgeistW, ouuan, shawlleyw, Tiphereth-A 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用