字符串
字符串可以看做一种顺序存储且元素为字符的顺序表。
字符串匹配
字符串匹配的应用场景非常广泛,但凡涉及到搜索的,都需要使用该算法。因此最大程度降低该算法的复杂度开销是十分关键的。字符串匹配的任务定义为:给定一个模板串 \(s\ (1\le |s|\le n)\) 和一个模式串 \(t\ (1\le |t|\le m)\),我们需要在 \(s\) 中查找 \(t\) 出现的位置。
暴力匹配。最朴素的字符串匹配很好理解,枚举 \(s\) 的每一个字符作为起始位置,然后与 \(t\) 匹配即可,时间复杂度为 \(O(nm)\)。数据量一大,时间开销就会爆炸。
KMP 算法。该算法在约 50 年前被三位大佬提出,算法就以这三位的首字母命名,感兴趣的可以看一下原论文:FAST PATTERN MATCHING IN STRINGS。该算法可以以 \(O(n+m)\) 的时间复杂度完成上述字符串匹配任务。具体地:
- 在暴力匹配方法中,每次都会将模式串 t 右移一位重新与 s 匹配,能不能多移动几位呢?答案是可以的。为了不浪费已经匹配过的子串,我们对模式串 \(t\) 维护出一个右移的位数表,记作
next
。其中next[j]
表示 \(t\) 的第 \(j\) 位可以右移的位数。显然next
数表只需要根据 \(t\) 即可维护出来; - 接下来就可以像暴力匹配那样进行匹配了,只不过现在每次失配时,模式串 \(t\) 右移的位数从原来的 \(1\) 变成了
next[j]
了(假设当前模式串匹配到第 \(j\) 位)。
下面给出代码示例。为了编码方便,所有下标均从 \(1\) 开始。
1)维护 next 数表:
2)字符串匹配: