KMP算法

前缀函数

定义

对于字符串s，其前缀函数定义为
π ( i ) = m a x { k : s [ 0... k − 1 ] = s [ i − ( k − 1 ) . . . i ] } k = 0... i \pi (i) = max\{k : s[0...k - 1] = s[i - (k - 1)...i]\}\\k = 0 ... i π(i)=max{k:s[0...k−1]=s[i−(k−1)...i]}k=0...i

例：字符串 “aabaaab”

$\pi [0]=0$（子串 “a” → 0）

$\pi [1]=1$（子串 “aa” → 前缀 “a” 与后缀 “a” 匹配 → 1）

$\pi [2]=0$（子串 “aab” → 0）

$\pi [3]=1$（子串 “aaba” → 前缀 “a” 与后缀 “a” → 1）

$\pi [4]=2$（子串 “aabaa” → 前缀 “aa” 与后缀 “aa” → 2）

$\pi [5]=2$（子串 “aabaaa” → 前缀 “aa” 与后缀 “aa” → 2）

$\pi [6]=3$（子串 “aabaaab” → 前缀 “aab” 与后缀 “aab” → 3）

性质

对于字符串 $S$，其前缀函数 ($\pi [i]$) 表示子串 ($S[\mathrm{0..}i]$) 的最长相等真前缀和真后缀的长度。

真前缀 / 后缀（不包含整个子串）

取值范围：($0\le \pi [i]\le i$)

非严格递增： 对于任意 i，有 ($\pi [i+1]\le \pi [i]+1$)。 即每次递推时，($\pi$) 值最多增加 1。

代码模板

#include <bits/stdc++.h>
using namespace std;

string s;

int main () {
    cin >> s;
    
    int n = s.size();
    
    s = " " + s;                // 将字符串下标调整为从1开始
    
    vector<int> pi(n + 1);      // 创建前缀函数数组，长度为n+1
    
    for (int i = 2; i <= n; i ++) {  // 从第2个字符开始计算（i = 1时, pi[1] = 0）
        int len = pi[i - 1];          // 利用前一个位置的前缀函数值
        
        // 当当前字符与前缀字符不匹配时，回溯len的值
        while (len > 0 && s[len + 1] != s[i])
            len = pi[len];
        
        // 如果找到匹配的前缀字符，则len加1
        if (s[len + 1] == s[i])
            len ++;
        
        pi[i] = len;                  // 记录当前位置的前缀函数值
    }
    
    // 输出调整后的字符串
    for (int i = 1; i <= n; i ++) 
        cout << s[i] << " ";
    cout << endl;
    
    // 输出前缀函数数组
    for (int i = 1; i <= n; i ++)
        cout << pi[i] << " ";
    cout << endl;
    
    return 0;
}

KMP函数

名字缘由：由 Knuth、Pratt 和 Morris 在 1977 年共同发布。

过程

摘自OI-wiki

匹配过程

1. 预处理模式串：计算前缀函数 π。

2. 主循环匹配

   使用两个指针 i（主串）和 j（模式串）。

   当 T[i] == P[j] 时，两指针同时前进。

   当T[i] != P[j]时：

   ​ 根据前缀函数 π[j-1] 决定模式串应该向右滑动多远（即 j = π[j-1]）。

   ​ 若 j 回退到 0 仍不匹配，则 i 前进一位。

   ​ 当 j 到达模式串末尾时，说明找到一个匹配，记录位置并继续匹配。

示例演示：

主串 T = "ABABDABACDABABCABAB"
模式串 P = "ABABCABAB"
前缀函数 π = [0, 0, 1, 2, 0, 1, 2, 3, 4]

初始匹配

T: ABABDABACDABABCABAB
P: ABABCABAB
      ^ 失配（i=4, j=4）

π[3] = 2，模式串右滑 4 - 2 = 2 位，从 j=2 继续匹配。

第二次匹配：

T: ABABDABACDABABCABAB
P:   ABABCABAB
          ^ 失配（i=7, j=5）

π[4] = 0，模式串右滑 5 - 0 = 5 位，从 j=0 继续匹配。

第三次匹配：

T: ABABDABACDABABCABAB
P:         ABABCABAB
                   ^ 匹配成功（i=15, j=9）

代码模板

前缀函数计算：

compute_prefix 函数生成模式串的前缀函数数组 pi，其中 pi[i] 表示模式串前 i+1 个字符的最长相等前缀和后缀长度。

KMP 搜索：

函数在文本中查找模式串的所有出现位置：

使用前缀函数数组 pi 避免不必要的回溯，时间复杂度为 $O(n+m)$。

当找到匹配时，记录起始位置并继续搜索后续可能的匹配。

复杂度：$O(n+m)$

#include <bits/stdc++.h>
using namespace std;

string a, b;
int cnt = 0;

// 构建pi数组
vector<int> cp(const string& pattern) {
	int m = pattern.size();
	vector<int> pi(m, 0);
	int j = 0;
	
	for (int i = 1; i < m; i++) {
		// 不匹配时回退
		while (j > 0 && pattern[i] != pattern[j]) 
			j = pi[j - 1];
		
		// 匹配成功
		if (pattern[i] == pattern[j]) 
			j++;
		
		pi[i] = j;
	}
	
	return pi;
}

// KMP算法：在文本text中查找所有模式串pattern的出现位置
vector<int> kmp_search(const string& text, const string& pattern) {
	int n = text.size();
	int m = pattern.size();
	vector<int> pi = cp(pattern);
	vector<int> matches;  // 存储匹配的起始位置
	int j = 0;  // 模式串的当前匹配位置
	
	for (int i = 0; i < n; i++) {
		// 回溯到上一个可能的匹配位置
		while (j > 0 && text[i] != pattern[j]) 
			j = pi[j - 1];  
		
		if (text[i] == pattern[j]) 
			j++;
		
		// 找到一个完整匹配
		if (j == m) {  
			cnt ++;			// 记录pattern出现次数
			matches.push_back(i - m + 1);  // 记录匹配的起始位置
			j = pi[j - 1];  // 继续寻找下一个匹配
		}
	}
	
	return matches;
}

int main() {
	cin >> a >> b;
	
	vector<int> positions = kmp_search(a, b);
	
	for (int pos : positions) {
		printf("%d ", pos);		// 出现位置
	}
	
	printf("\n%d", cnt);		// 出现次数
	
	return 0;
}