字符串

字符串可以看做一种顺序存储且元素为字符的顺序表。

字符串匹配

字符串匹配的应用场景非常广泛，但凡涉及到搜索的，都需要使用该算法。因此最大程度降低该算法的复杂度开销是十分关键的。字符串匹配的任务定义为：给定一个模板串 \(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 数表：

for (int i = 2, j = 0; i <= m; i++) {
    while (j && t[i] != t[j + 1])
        // 未匹配上则不断回溯
        j = ne[j];

    if (t[i] == t[j + 1])
        // 匹配上了则j指针后移一位
        j++;

    ne[i] = j;
}

2）字符串匹配：

for (int i = 1, j = 0; i <= n; i++) {
    while (j && news[i] != newt[j + 1])
        // 未匹配上则不断回溯
        j = ne[j];

    if (news[i] == newt[j + 1])
        // 匹配上了则j指针后移一位
        j++;

    if (j == m) {
        // 匹配完全，则统计并且回溯
        cnt++;
        j = ne[j];
    }
}

字符串

字符串匹配

字典树 (Trie)