KMP入门

一、引例

题目描述

原题来自：HDU 2087

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入格式

输入数据为多组数据，读取到 # 字符时结束。每组数据仅有一行，为由空格分开的花布条和小饰条。花布条和小饰条都是用可见 ASCII 字符表示的，不会超过 $1000$ 个字符。

注意：这个 # 应为单个字符。若某字符串开头有 #，不意味着读入结束！

输出格式

对于每组数据，输出一行一个整数，表示能从花纹布中剪出的最多小饰条个数。

样例

abcde a3
aaaaaa aa
#

0
3

数据范围与提示

对于全部数据，字符串长度 $\le 1000$。

思路1

首先考虑采用哈希。

思路2——KMP算法

考虑一种更快、代码量更少的方法——KMP算法。

我们令第一个字符串为 s，第二个字符串为 t，需要求出 t 在 s 中不重叠的匹配个数。

KMP算法的思想：在匹配 s 的过程中，每次遇到失配的点 s[i]!=t[j]，我们应该快速地选择 t[0...j-1] 的 border（参见字符串哈希），实现不往回移动 i 的前提下，快速地完成 s[0...i-1] 的后缀与 t 串前缀的最长匹配，由于外层下标 i 从左至右只走一遍，每次匹配时，j 同 i 一起向前移动，撤回border的次数一定小于向前移动的次数，因此整体时间复杂度为 $O(n)$。

因此，问题转换为如何求出串 t 所有前缀的最大非平凡border，即实现一个前缀函数。

前缀函数

定义 nx[i] 表示 t[0...i] 的最长非平凡border的长度，特别地，nx[0] 为 0。

从 t[1] 开始逐个求前缀函数 t[i] 的过程如下：

1. 设border长度的初值 int j = 0;
2. while (j && t[i]!=t[j]) j = nx[j-1];// t[i] 失配时，从长到短依次尝试 t[i-1] 的每一个border
3. if (t[i] == t[j]) ++j;// 若找到了某个border，可以匹配 t[i]，匹配长度加 1。
4. nx[i] = j;// 记录 t[i] border的长度

void match() {
	for (int i = 1, j = 0; t[i]; ++i) {
		while (j && t[i]!=t[j]) j = nx[j-1];
		if (t[i] == t[j]) ++j;
		nx[i] = j;
	}
}