算法--Brute-Force算法和KMP算法笔记

  模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的子串,这就是模式匹配。

1、Brute-Force模式匹配算法

  Brute-Force算法的思想是:在主串S=”s1,s2,s3,…,sn”中的第一个字符与模式串T=”t1,t2,t3,…tn”中的第一个字符开始匹配,如果相等,则比较S串第二个字符和T串中的第二个字符。如果T串中的每个字符都与S串中连续的字符匹配成功,则返回S串中第一个下标的位置。如果匹配不想等,则将S中的第二个字符与T中第一个字符匹配,然后一次匹配下去。

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
# include<stdio.h>
/*
S[] 是主串
T[] 是模式串
pos 是指在S中第pos个位置开始匹配,我设置为0
return i 如果匹配成功,返回 子串在S中第一个位置的下标。 匹配失败,返回-1
*/
int index_BF(char S[],char T[], int pos)
{
int i = pos;//i是S中的位置
int j = 0; //j是T中的位置
while(S[i] != '\0' && T[j] != '\0'){
if(S[i+j] == T[j]){ //两个字符判断成功,则j+1.判断下一个字符
j++;
}else{ //判断失败,则将T第一个与S第二个匹配 。于是i+1,S取下一个。j=0,T重新开始匹配
i++;
j = 0;
}
}
if(T[j] == '\0'){ //T中所有字符与S中连续字符匹配成功。
return i;
}else{
return -1;
}
}
int main()
{
char S[] = "qwertyuiop";
char T[] = "io";
int pos = 0;
int index = index_BF(S,T,pos);
printf("%d",index);
return 0;
}

2、KMP模式匹配算法

  看了一晚上终于明白KMP算法。KMP算法使用一种预先处理的方式。首先将模式串自我匹配。
Alt text
这个图中我们可以看到,刚开始出现的是a,b,c,于是我们就在模式串中找到a,b,c。通过这种自我匹配的方式,找到模式串可能出现的位置。
那么模式串是怎样自我匹配的呢。这里有前缀和后缀的概念。
Alt text
这样就能判断字符串前部和后部是不是有重复。

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
#include <stdio.h>  
#include <string.h>

int next[32] = {-999};

/*这个函数就是对模式串预处理
将预处理的信息保存到next数组中。
整个程序只运行一次这个函数

*/
void get_next(char T[])
{
int k = -1;
int j = 0;
int tLen = strlen(T);
next[j] = k; //模式串第一个设置为-1
while (j < tLen - 1)
{
if ( (k == -1) || (T[j] == T[k]) )
{
k++;
j++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int index_KMP(char S[], char T[], int pos)
{
int i = pos;
int j = 0;
int sLen = strlen(S);
int tLen = strlen(T);
while ( i < sLen && j < tLen )
{
/* j = -1 表示next[0]*/
if ( (j == -1) || S[i] == T[j])
{
i++;
j++;

}
else
{
printf("j == %d\t",j);
j = next[j]; //next[j]里面存的是开始匹配的位置。

}
}

if (tLen == j) //表示整个T都对比完了,匹配成功了
{
return i - tLen ;
}
else
{
return -1;
}
}

int main(void)
{
char s[] = "qwertyuiop";
char t[] = "io";
int i;
int pos = 0;
int index;
// 预处理next数组
get_next(t);
index = index_KMP(s, t, pos);
printf("%d\n", index);

return 0;
}