当前位置：首页 > news >正文

kmp の笔记

news 来源：原创 2024/5/19 5:50:23

预备知识

1.前后缀

s[i] 表示字符串 S 第 i 个位置的字母 ，下标从 1 开始

Prefix_s [i] 表示 S 的长度为 i 的前缀
Suffix_s [i] 表示 S 的长度为 i 的后缀

2. border

如果一个字符串的同长度前缀和后缀完全相同
称为字符串的一个 border

S = bbabbab

b 和 bbab 为这个字符串的两个 border

3.border 的性质(很重要)

1.考虑 prefix[i] 的所有 border 去掉最后一个字母就会变成 prefix[i-1] 的一个 border(求nex数组的原理)
2.border具有传递性， S的border 的 border 一定是 S 的border(求nex数组的原理)
S 的最大border 在串里最少出现两次，S最大border 的子border 在串中最少出现四次，依次 × 2
3.p 是 S 的周期那么 |S| - p 一定是 S 的 border

4. 循环周期

S = bbabbab

循环周期

bba
bbabba
bbabbab

循环节

满足 $p ∣∣ s ∣$ 时，把 p 称作 S 的一个循环节

对于 kmp 的理解

1.求nex数组

int nex[10001];
void GetNext(string ss)
{
	int len = ss.size();
	
	nex[1] = 0;
	
	for(int i=2;i<=len;i++){
		nex[i] = nex[i-1];
		
		//先继承 ， 继承多少决定是否能往下循环
		
		while(nex[i] && ss[i-1] != ss[nex[i]]) nex[i] = nex[nex[i]];
		//在 pre[i] 的所有 border 中找到一个最大子 border
		
		// nex[i] 的子 border 是 nex[nex[i]] 不一定是 nex[i-1] 所以递归找到的第一个 一定是最大子 border 因为 子border的长度一定比本身短
		
		nex[i] += (ss[i-1] == ss[nex[i]]); 
		// ss[i-1] 后缀新加字母
		// ss[nex[i]] 是前缀新加字母 
	}	
}
// bbabbab
/*
考虑 prefix[i] 的所有 border 去掉最后一个字母 就会变成 prefix[i-1] 的一个 border
从 prefix[i-1] 推 prefix[i] 就是对 prefix[i-1] 所有 border 进行加位操作
*/

KMP字符串匹配

#include<bits/stdc++.h>
using namespace std;
         
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;
 
int nex[N],k,ans,n;
string s1,s2;
int len1,len2;
 
void init(string s){
	
	n = s.size();	
	
    for(int i=2;i<=n;i++){
        nex[i] = nex[i-1];
        while(nex[i] && s[nex[i]] != s[i-1]) nex[i] = nex[nex[i]];
        nex[i] += (s[i-1] == s[nex[i]]);
    }
}
// bbabbab

void kmp(string s1,string s2){
	
	for(int i=1,j=0;i<=len1;i++){
		
		while(j && s1[i-1] != s2[j]) j = nex[j];
		
		// j 保证 border 链非空
		
		if(s1[i-1] == s2[j]) j++;
		
//		cout << j << "\n" ;
		
		if(j == len2) cout << i - len2 + 1 << "\n" , j = nex[j] ;
	}
}
 
int main(){
     
    IOS;
    
    cin >> s1 >> s2 ;
    
    len1 = s1.size();
	len2 = s2.size();
    
    init(s2);
     
    kmp(s1,s2); 
    
    
	for(int i=1;i<=len2;i++){
		cout << nex[i] << " " ;
	}
     
     
         
    return 0;
}