模式匹配(数据结构)

朴素模式匹配算法

#include 
#include 
#include 
#define MaxSize 255

typedef struct{
	char ch[MaxSize];
	int length;
}SString;

//初始化
SString InitStr(SString &S){
	S.length=0;
	return S;
} 

//给串赋值 
SString SetStr(SString &S){
	char c;
	int i=1;
	scanf("%c",&c);
	while(c!='\n'){
		S.ch[i++]=c;
		S.length++;
		scanf("%c",&c);
	}
	return S;
} 

//朴素模式匹配算法
int Index(SString &S,SString &D){
	int i=1,j=1;
	while(i<=S.length&&j<=D.length){
		if(S.ch[i]==D.ch[j]){//匹配成功 
			++i;
			++j;
		}
		else{//匹配失败 
			i=i-j+2;
			j=1;
		}
	}
	if(j>D.length){
		return i-D.length;
	}
	else return 0;
} 

int main(){
	SString S;//主串 
	SString D; //子串
	InitStr(S);
	InitStr(D);
	printf("输入主串:");
	SetStr(S);
	printf("输入子串:"); 
	SetStr(D);
	printf("-------朴素模式匹配:--------\n");
	int i;
	i = Index(S,D);
	if(i>0) printf("匹配成功，位置是:%d",i);
	else printf("匹配失败");
	return 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

KMP算法

#include 
#include 
#include 
#define MaxSize 255

typedef struct{
	char ch[MaxSize];
	int length;
}SString;

//初始化
SString InitStr(SString &S){
	S.length=0;
	return S;
} 

//给串赋值 
SString SetStr(SString &S){
	char c;
	int i=1;
	scanf("%c",&c);
	while(c!='\n'){
		S.ch[i++]=c;
		S.length++;
		scanf("%c",&c);
	}
	return S;
} 

//根据子串来求解GetNext
void Get_Next(SString &D,int *next){
	int i=1,j=0;
	next[1]=0;
	while(i<D.length){
		if(j==0||D.ch[i]==D.ch[j]){
			++i;++j;
			next[i]=j;//如果Pi=Pj,则next[j+1]=next[j]+1 
		}
		else{
			j=next[j];
		}
	}
} 

//对next进行优化
void Get_NextVal(SString D,int *next,int *nextval){
	nextval[1]=0;
	for(int j=2;j<D.length;j++){
		if(D.ch[next[j]]==D.ch[j])
			nextval[j]=nextval[next[j]];
		else
			nextval[j]=next[j];
	}
}

//KMP算法 
int Index_KMP(SString &S,SString &D,int *next){
	int i=1,j=1;
	while(i<=S.length&&j<=D.length){
		if(j==0||S.ch[i]==D.ch[j]){
			++i;++j;//继续比较 
		}
		else
			j=next[j];//模式串向右移动 
	}
	if(j>D.length)
		return i-D.length;//匹配成功 
	else
		return 0;
} 

//输出next数组
void PrintNext(SString D,int *next){
	for(int i=1;i<D.length+1;i++){
		printf("%d ",next[i]);
	}
	printf("\n");
} 

int main(){
	SString S;//主串 
	SString D; //子串
	InitStr(S);
	InitStr(D);
	printf("输入主串:");
	SetStr(S);
	printf("输入子串:"); 
	SetStr(D);
	printf("----------------KMP----------------\n");
	int next[D.length+1];
	Get_Next(D,next);
	printf("输出next数组:");
	PrintNext(D,next);
	printf("输出优化后next数组:");
	int nextval[D.length+1];
	Get_NextVal(D,next,nextval);
	PrintNext(D,nextval);
	
	int loc;
	loc=Index_KMP(S,D,next);//使用优化前的next数组 
//	loc=Index_KMP(S,D,nextval);//使用优化后的next数组 
	if(loc>0) printf("匹配成功，位置是:%d",loc);
	else printf("匹配失败");
	return 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
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
102
103
104
105