【KMP】KMP字符串匹配
2021-03-17 16:38:00 # ACM

#前言

学自OI-wiki 前缀函数与kmp

##第二个优化

从第二个优化开始我看的时间比较久，如图部分

其中公式

看了挺久，主要是第二个部分到第三个部分，关于这个转换，在例图展示中如

因为 s[0…3] == s[(i-3)…i] && s[0…1] == s[(i-1)…i]，所以 s[0…1] == s[2…3] 的，所以指针 j 就可以直接转到 pi[j-1] 的地方，开始比较 s[j] 与 s[i+1];

真的很佩服这三个人（跪下）

j指针转移样例

例题

洛谷P3375 【模板】KMP字符串匹配

题链

字符以 0 为开头写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define mod 99999997
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
char s[MS]; // 文本串 
char e[MS]; // 模式串 
LL hs,he;  	// 串长 
LL kp[MS]; 	// 模式串 e 的前缀数组 
LL kps[MS];	// 文本串 s 的前缀数组 
LL ac[MS],tac;	// 记录答案 

void kmp_e(){ // 求模式串 e 的前缀数组 
	kp[0] = 0;
	for(int i=1;i<he;i++){
		int j = kp[i-1];
		while(j>0 && e[j] != e[i]) j = kp[j-1];
		if(e[j] == e[i]) j++;
		kp[i] = j;
	}
}

void kmp_s(){ // 求文本串 s 的前缀数组  
	int j = 0;
	for(int i=0;i<hs;i++){
		while(j>0 && s[i] != e[j]) j = kp[j-1];
		if(s[i] == e[j]) j++;
		kps[i] = j; // 记录 
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin >> s;
	cin >> e;
	hs = strlen(s);
	he = strlen(e);
	kmp_e();
	kmp_s();
	for(int i=0;i<hs;i++){ // 若 s 前缀数组的值 与 模式串 e 相等 则记录位置 
		if(kps[i] == he){
			ac[++tac] = i-he+1+1;
		}
	}
	for(int i=1;i<=tac;i++){
		cout << ac[i] << endl;
	}
	for(int i=0;i<he;i++){
		cout << kp[i] << " ";
	}
	cout << endl;
	

	return 0;
}

时隔一个多月还是写一写以 1 为开头的kmp;

感觉 1 开头的舒服些；

领悟了下 j 指针总是在模式串上跑的；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 1000009 

int n,m;
char s1[MS];
char s2[MS];
int kmps1_s2[MS];
int kmps2[MS];
int ac[MS];

int main() {
	ios::sync_with_stdio(false);
	cin >> s1+1;
	cin >> s2+1;
	int h1 = strlen(s1+1);
	int h2 = strlen(s2+1);
	for(int i=2,j=0;i<=h2;i++){
		while(j && s2[i] != s2[j+1]) j = kmps2[j];
		if(s2[i] == s2[j+1]) j++;
		kmps2[i] = j;
	}
	for(int i=1,j=0;i<=h1;i++){
		while(j && s1[i] != s2[j+1]) j = kmps2[j]; // j 指针总是在模式串上的 kmp 跑 
		if(s1[i] == s2[j+1]) j++;
		kmps1_s2[i] = j;
	}
	int tot = 0;
	for(int i=1;i<=h1;i++){
		if(kmps1_s2[i] == h2){
			ac[++tot] = i-h2+1;
		}
	}
	for(int i=1;i<=tot;i++){
		cout << ac[i] << "\n";
	}
	for(int i=1;i<=h2;i++){
		cout << kmps2[i] << " ";
	}
	cout << "\n";
	
	
	return 0;
}

又时隔4个多月，用fft板子试试字符串匹配，当然求border还是kmp；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 #include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define MS 1000009
#define LL long long

int n,m;
char s1[MS], s2[MS];
int kmps2[MS];
int h1, h2;
double A[MS], B[MS], S[MS];
double sumB, qzA[MS], jjSA[MS<<1];

// 洛谷 P3803 【模板】多项式乘法（FFT）
// MS = 1e6 
// time: max( 800ms ) 
// ========================================================================================
typedef complex<double> comp;
const double PI = acos(-1);
const int N = (1<<21)+10; // 长度为原长度向上的2^n, 再乘 2  
int lim, r[N];
comp a[N], b[N];

void fft(comp * a, int type) {
	for(int i = 0; i < lim; i ++)
		if(i < r[i]) swap(a[i], a[r[i]]);
	for(int i = 1; i < lim; i <<= 1) {
		comp x(cos(PI / i), type * sin(PI / i));
		for(int j = 0; j < lim; j += (i << 1)) {
			comp y(1, 0);
			for(int k = 0; k < i; k ++, y *= x) {
				comp p = a[j + k], q = y * a[j + k + i];
				a[j + k] = p + q; a[j + k + i] = p - q;
			}
		}
	}
}

// [0, n], [0, m]
void get(double *c1, int n, double *c2, int m){ 
	for(int i = 0; i <= n; i ++) a[i] = c1[i];
	for(int i = 0; i <= m; i ++) b[i] = c2[i];
	int l = 0;
	for(lim = 1; lim <= n + m; lim <<= 1) ++ l;
	for(int i = 0; i < lim; i ++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
		
	fft(a, 1), fft(b, 1);
	for(int i = 0; i <= lim; i ++) a[i] *= b[i];
	fft(a, -1);
	// 得出系数 
	for(int i = 0; i <= n + m; i ++) jjSA[i] = (LL)(0.5 + a[i].real() / lim);
}
// ========================================================================================

void kmp(char *s, int len){
	for(int i=1,j=0;i<len;i++){
		while(j && s[i] != s[j]) j = kmps2[j-1];
		if(s[i] == s[j]) j++;
		kmps2[i] = j;
	}
}

int main() {
	scanf("%s",s1); getchar();
	scanf("%s",s2); getchar();
	int h1 = strlen(s1), h2 = strlen(s2);
	for(int i=0;i<h1;i++) A[i] = s1[i]-'a'+1; // 文本串 
	for(int i=0;i<h2;i++) B[i] = s2[i]-'a'+1; // 模式串 
	for(int i=0;i<h2;i++) S[i] = B[h2-i-1];	  // 模式串翻转 
	
	// ∑B(i)^2 => sumB
	for(int i=0;i<h2;i++) sumB += B[i]*B[i];
	
	// ∑A(i)^2 的前缀 => qzA[]
	qzA[0] = A[0]*A[0];
	for(int i=1;i<h1;i++) qzA[i] = qzA[i-1] + A[i]*A[i];
	
	// ∑S(i)A(j) => jjSA[]
	// i+j=x
	get(S, h2-1, A, h1-1);
	
	// P(x) = sumB + qzA[x] - qzA[x-h2] - 2*jjSA[x]
	for(int x=h2-1;x<h1;x++){
		double P;
		if(x == h2-1) P = sumB + qzA[x] - jjSA[x]*2;
		else P = sumB + qzA[x] - qzA[x-h2] - jjSA[x]*2;
		if(abs(P) < eps){
			printf("%d\n",x-h2+2);
		}
	}
	
	kmp(s2, h2);
	for(int i=0;i<h2;i++){
		printf("%d ",kmps2[i]);
	}
	
	
	
	return 0;
}
Prev
2021-03-17 16:38:00 # ACM
Next