KMP 算法

1 KMP 算法简介

Knuth-Morris-Pratt 算法（简称 KMP）是一种字符串匹配算法，可以在 O(n + m) 的时间复杂度内完成字符串匹配。

2 前缀函数

字符串前缀是指从串首开始到某一位置 $i$ 结束的一个特殊子串。字符串 $S$ 的以 $i$ 结尾的前缀表示为：$Prefix(S,i)=S[0\dots i]$。真前缀指除了 $S$ 本身外 $S$ 的前缀。

字符串后缀是指从某一位置 $i$ 开始到串尾结束的一个特殊子串。字符串 $S$ 的以 $i$ 开始的后缀表示为：$Suffix(S,i)=S[i\dots |S|-1]$。真后缀指除了 $S$ 本身外 $S$ 的后缀。

前缀函数：给定一个长度为 $n$ 的字符串 $S$ （这里定义下标从 $1$ 开始），它的前缀函数被定义为一个长度为 $n$ 的数组 $nxt$。 $nxt[i]$ 为:

1. 如果子串 $S[1,i]$ 有一对相等的真前缀与真后缀，即 $S[1\dots k]$ 和 $S[i-k+1\dots i]$，则前缀函数 $nxt[i]=k$。
2. $nxt[i]$ 是所有对相等的真前缀与真后缀长度的最大值。
3. 如果不存在相等的一对真前缀与真后缀，则 $nxt[i]=0$。

注：$nxt[1]=0$

2.1 朴素算法求解前缀函数

void getnxt(char *p, int len) {
    nxt[1] = 0;
    for (int i = 2; i <= len; i++) {
        for (int j = i - 1; j >= 0; j--) { // 从最大的真前缀长度开始尝试
            bool flag = true;
            for (int x = 1, y = i - j + 1; x <= j; x++, y++) {
                if (p[x] != p[y]) {
                    flag = false;
                }
            }
            if (flag) { // 找到一对则终止
                nxt[i] = j;
                break;
            }
        }
    }
}

2.2 第一个优化

相邻的前缀函数值至多增加 1。当前仅当 $S[i+1]=S[nxt[i]+1]$ 此时 $nxt[i+1]=nxt[i]+1$，其余情况要么维持不变、要么减小。

void getnxt(char *p, int len) {
    nxt[1] = 0;
    for (int i = 2; i <= len; i++) {
        for (int j = nxt[i - 1] + 1; j >= 0; j--) { // 修改 j = i - 1 -> j = nxt[i - 1] + 1
            bool flag = true;
            for (int x = 1, y = i - j + 1; x <= j; x++, y++) {
                if (p[x] != p[y]) {
                    flag = false;
                }
            }
            if (flag) {
                nxt[i] = j;
                break;
            }
        }
    }
}

2.3 第二个优化

当 $S[i+1]\ne S[nxt[i]+1]$ 时，我们希望找到对于子串 $S[1\dots i]$ 仅次于 $nxt[i]$ 的第二长度 $j$，使得在位置 $i$ 的前缀性质仍得以保持，即 $S[1\dots j]=S[i-j+1\dots i]$ :

$$\stackrel{nxt[i]}{\overbrace{\underset{j}{\underbrace{s_1{s}_2}}{s}_3{s}_4}}\dots \stackrel{nxt[i]}{\overbrace{s_{i-3}{s}_{i-2}\underset{j}{\underbrace{s_{i-1}{s}_i}}}}{s}_{i+1}$$

如果我们找到了这样的长度 $j$，那么仅需要再次比较 $S[i+1]$ 和 $S[j+1]$。如果它们相等，那么就有 $nxt[i+1]=j+1$，否则重复此过程，直到 $j=0$ 如果 $S[i+1]\ne S[1]$，则 $nxt[i+1]=0$。

由上图可知有 $S[1\dots nxt[i]]=S[i-nxt[i]+1\dots i]$ 所以对于 $j$ 有 $S[1\dots j]=S[i-j+1\dots i]=S[nxt[i]-j+1\dots nxt[i]]$ 也就是说 $j$ 等价于子串 $S[nxt[i]]$ 的前缀函数值，即 $j=nxt[nxt[i]]$。

最后我们把代码写一下：

void getnxt(char *p, int len) {
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}

3 KMP 算法

给定一个主串 $S$ 和模式串 $P$，请找到 $P$ 在 $S$ 中所有出现位置。

#include <iostream>
using namespace std;

const int N = 1e5 + 5, M = 1e6 + 5;
char s[M], p[N]; // 主串，模式串
int nxt[N], n, m;

void getnxt(char *p, int len) {
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}

int main() {
    cin >> n >> p + 1 >> m >> s + 1;

    getnxt(p, n);
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && s[i] != p[j + 1]) j = nxt[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n) { // 匹配成功
            cout << i - n << endl;
            j = nxt[j];
        }
    }

    return 0;
}

4 练习题目

1. 洛谷 P3375.【模板】KMP
2. Jouier 2195. 剪花布条
3. Jouier 2196. Power Strings

@author lllyouo
@date 2024-09-24
@problem Jouier 2196. Power Strings

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 5;
char s[N];
int nxt[N], n;

void getnxt(char *p, int len) {
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}

int main() {
	while (cin >> s + 1) {
		if (s[1] == '.' && strlen(s + 1) == 1) break;
		n = strlen(s + 1);
	    getnxt(s, n);

		if (n % (n - nxt[n]) == 0) {
			cout << n / (n - nxt[n]) << endl;
		} else {
			cout << 1 << endl;
		}
	}

    return 0;
}