数据结构之串的匹配

串的匹配应用十分广泛，比如搜索引擎、拼写检查、语言翻译、数据压缩等等，都需要进行串的匹配。

串的模式匹配设有两个字符串 S 和 T ，设 S 为主串（正文串），T 为子串（模式），在主串 S 中查找与模式 T 相匹配的子串，如果匹配成功，确定相匹配的子串中第一个字符在主串 S 中出现位置。下面介绍两种算法：BF 算法和 KMP 算法。

一、BF算法

1、分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前待比较的字符位置。
2、如果比较未到结尾，则循环执行以下操作：
① S.ch[ i ] 和 T.ch[ j ] 比较，若相等，则 i++; j++; 继续比较后续字符。
② 若不等，指针后退重新匹配，从主串的下一个字符(i = i - j + 2)起再重新和模式的第一个字符(j = 1)比较。
3、如果 j > T.length，说明匹配成功，返回和模式 T 第一个字符相等的字符在主串中的序号(i - T.length)，否则失败，返回0。

该算法的时间复杂度为 O(m × n)

代码如下：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAXSIZE 20
 5 typedef struct
 6 { // 定义数组存储字符串
 7     char ch[MAXSIZE+1];
 8     int length;
 9 }String;
10 int index_BF(String S, String T);
11 int main()
12 {
13     int flag;
14     String S, T;
15     printf("请输入主串S:");
16     gets(S.ch + 1);
17     S.length = strlen(S.ch+1);
18     S.ch[0] = (char)S.length;
19     printf("请输入模式串T:");
20     gets(T.ch + 1);
21     T.length = strlen(T.ch+1);
22     T.ch[0] = (char)T.length;
23     flag = index_BF(S, T);
24     if (flag)
25         printf("匹配成功，在第%d位。
", flag);
26     else
27         printf("匹配失败，未找到该子串。
");
28 }
29 int index_BF(String S, String T)  // BF算法
30 {
31     int i = 1,j = 1;
32     while (i <= S.length && j <= T.length) // 两串均未到达串尾
33     {
34         if (S.ch[i] == T.ch[j]) { i++; j++; } // 继续向后匹配字符
35         else { i = i - j + 2; j = 1;}  // 若不相等，回溯
36     }
37     if (j > T.length)
38         return i - T.length;
39     else
40         return 0;
41 }

效果如下：

运行结果

二、KMP算法

此算法的改进在于，每当每当匹配过程中出现字符比较不相等时，不需要回溯 i 指针，而是利用已经得到的 “部分匹配” 的结果将模式向右 “滑动” 尽可能远的一段距离，继续进行比较。而滑动的具体距离，由 get_next 函数确定，具体原理不再描述。

时间复杂度为 O(m + n)，较BF算法有很大提升。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAXSIZE 20
 5 typedef struct
 6 { // 定义数组存储字符串
 7     char ch[MAXSIZE + 1];
 8     int length;
 9 }String;
10 int index_KMP(String S, String T, int next[]);
11 void get_next(String T, int next[]);
12 int main()
13 {
14     int flag;
15     int next[MAXSIZE] = {0};
16     String S, T;
17     printf("请输入主串S:");
18     gets(S.ch + 1);
19     S.length = strlen(S.ch + 1);
20     S.ch[0] = (char)S.length;
21     printf("请输入模式串T:");
22     gets(T.ch + 1);
23     T.length = strlen(T.ch + 1);
24     T.ch[0] = (char)T.length;
25     get_next(T, next);
26     flag = index_KMP(S, T, next);
27     if (flag)
28         printf("匹配成功，在第%d位。
", flag);
29     else
30         printf("匹配失败，未找到该子串。
");
31 }
32 void get_next(String T, int next[])
33 {
34     int j = 0, i = 1;
35     next[1] = 0;
36     while (i < T.length)
37     {
38         if (j==0 || T.ch[i] == T.ch[j]) { i++; j++; next[i] = j; }
39         else j = next[j];
40     }
41 }
42 int index_KMP(String S, String T, int next[])
43 {
44     int i = 1, j = 0;
45     while (i <= S.length && j <= T.length)
46     {
47         if (j == 0 || S.ch[i] == T.ch[j]) { i++; j++; }
48         else j = next[j];
49     }
50     if (j > T.length)
51         return i - T.length;
52     else
53         return 0;
54 }


效果如下：

在这里插入图片描述

以上就是两种最常用的串匹配算法