数据结构之串的匹配

  串的匹配应用十分广泛，比如搜索引擎、拼写检查、语言翻译、数据压缩等等，都需要进行串的匹配。   串的模式匹配设有两个字符串 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)

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXSIZE 20 typedef struct { // 定义数组存储字符串 char ch[MAXSIZE+1]; int length; }String; int index_BF(String S, String T); int main() { int flag; String S, T; printf("请输入主串S:"); gets(S.ch + 1); S.length = strlen(S.ch+1); S.ch[0] = (char)S.length; printf("请输入模式串T:"); gets(T.ch + 1); T.length = strlen(T.ch+1); T.ch[0] = (char)T.length; flag = index_BF(S, T); if (flag) printf("匹配成功，在第%d位。\n", flag); else printf("匹配失败，未找到该子串。\n"); } int index_BF(String S, String T) // BF算法 { int i = 1,j = 1; while (i <= S.length && j <= T.length) // 两串均未到达串尾 { if (S.ch[i] == T.ch[j]) { i++; j++; } // 继续向后匹配字符 else { i = i - j + 2; j = 1;} // 若不相等，回溯 } if (j > T.length) return i - T.length; else return 0; }

二、KMP算法

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

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXSIZE 20 typedef struct { // 定义数组存储字符串 char ch[MAXSIZE + 1]; int length; }String; int index_KMP(String S, String T, int next[]); void get_next(String T, int next[]); int main() { int flag; int next[MAXSIZE] = {0}; String S, T; printf("请输入主串S:"); gets(S.ch + 1); S.length = strlen(S.ch + 1); S.ch[0] = (char)S.length; printf("请输入模式串T:"); gets(T.ch + 1); T.length = strlen(T.ch + 1); T.ch[0] = (char)T.length; get_next(T, next); flag = index_KMP(S, T, next); if (flag) printf("匹配成功，在第%d位。\n", flag); else printf("匹配失败，未找到该子串。\n"); } void get_next(String T, int next[]) { int j = 0, i = 1; next[1] = 0; while (i < T.length) { if (j==0 || T.ch[i] == T.ch[j]) { i++; j++; next[i] = j; } else j = next[j]; } } int index_KMP(String S, String T, int next[]) { int i = 1, j = 0; while (i <= S.length && j <= T.length) { if (j == 0 || S.ch[i] == T.ch[j]) { i++; j++; } else j = next[j]; } if (j > T.length) return i - T.length; else return 0; }