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”

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

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

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

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

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

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

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

性质

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

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

取值范围：(0 ≤ π [ i ] ≤ i 0 \leq \pi[i] \leq i0≤π[i]≤i)

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

代码模板

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

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)O(n+m)。

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

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

#include<bits/stdc++.h>usingnamespacestd;string a,b;intcnt=0;// 构建pi数组vector<int>cp(conststring&pattern){intm=pattern.size();vector<int>pi(m,0);intj=0;for(inti=1;i<m;i++){// 不匹配时回退while(j>0&&pattern[i]!=pattern[j])j=pi[j-1];// 匹配成功if(pattern[i]==pattern[j])j++;pi[i]=j;}returnpi;}// KMP算法：在文本text中查找所有模式串pattern的出现位置vector<int>kmp_search(conststring&text,conststring&pattern){intn=text.size();intm=pattern.size();vector<int>pi=cp(pattern);vector<int>matches;// 存储匹配的起始位置intj=0;// 模式串的当前匹配位置for(inti=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];// 继续寻找下一个匹配}}returnmatches;}intmain(){cin>>a>>b;vector<int>positions=kmp_search(a,b);for(intpos:positions){printf("%d ",pos);// 出现位置}printf("\n%d",cnt);// 出现次数return0;}