【KMP】模式串匹配
2020-06-22 22:51:00 # ACM

单模式串匹配

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
#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size

int n,m,k;
int p[MS],nex[MS];
char s[MS],ts[MS]; 

void get_next(char ts[],int len){
	int j=0,k=-1;
	nex[0] = -1;
	while(j<len-1){
		if(k==-1||ts[j] == ts[k]){
			// 当 ts[j+1] == ts[nex[j+1]] 时要跳过 
			if(ts[++j] == ts[++k])
				nex[j] = nex[k];
			else 
				nex[j] = k;
		}
		else k = nex[k];
	}
}

int kmp(char s[],char ts[],int h1,int h2){
	int i,j;
	i = j = 0;
	while(i<h1 && j<h2){
		if(s[i] == ts[j] || j == -1){
			i++ ,j++;
		}
		else j = nex[j];
	}
	if(j == h2) return i-j; // 返回从 0 开始的主串下标 
	else return -1;
}

int main() {
	cin >> s;
	cin >> ts;
	get_next(ts,strlen(ts));
	int ans = kmp(s,ts,strlen(s),strlen(ts));
	printf("%d\n",ans);
	
	return 0;
}

/*
input : 0123456789
		567
		
output: 5 
*/

向量匹配算法

我也不知道叫什么名字,就随便叫个名字，感觉也挺快的=.=

例如：主串为 abcbad 模式串为 cba

可以发现主串从0~2的向量值 和 2~4的向量值 与 模式串的向量值 相等 (向量值:ASCII值求和) .

存储主串中长度与模式串相等的向量值,遍历,若向量值相等,判断一遍即可 .

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
#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size

LL n,m,k,flag;
LL p[MS];
char s[MS],ts[MS]; 

int cmp(int i,int j,int len){
	while(j<len){ // 逐一比较 
		if(s[i] == ts[j]) ++i,++j;
		else return 0;
	}
	return 1;
}

int main() {
	cin >> s; // 主串 
	cin >> ts; // 模式串 
	int h1 = strlen(s); // 主串长度 
	int h2 = strlen(ts); // 模式串长度 
	// 记录模式串向量值 
	LL sum = 0;
	for(int i=0;i<h2;i++) sum += ts[i]; 
	// 记录主串每一段长度与模式串相同的向量值 
	for(int i=0;i<h2;i++) p[0] += s[i]; 
	for(int i=1;i+h2<=h1;i++) 
		p[i] = p[i-1] - s[i-1] + s[i+h2-1];
	// 匹配 
	for(int i=0;i<=h1-h2;i++){
		// 如果向量值相同 
		if(p[i] == sum){
			// 逐一比较 
			if(cmp(i,0,h2)){
				flag = 1;
				printf("%d\n",i); // 输出对应指针 
			} 
		}
	}
	if(!flag) printf("No\n");
	
	return 0;
}

/*
input : 0123456789
		567
		
output: 5 
*/
Prev
2020-06-22 22:51:00 # ACM
Next