数据结构（C语言）串的模式匹配BF算法

BF算法

BF(Brute Force)算法又称暴力算法，是一种普通的模式匹配算法，其思想是：从主串T第一个字符开始，取子串S长度个字符，这些字符分别与子串进行比较，若某位字符不相等，则在主串T起始字符向后推移一格与子串S再进行比较，直至在主串T遍历出与子串S相等的字符串。

串的顺序存储结构

typedef struct { char ch[MAXLEN + 1]; //存储串的一维数组 int length;//串的当前长度 }SString;

BF算法描述

int Index_BF(SString S, SString T) { int i = 1, j = 1;//i为从某个位置开始查找，可添加参数进行修改 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;//模式匹配不成功 } 主串回溯： i=i-j+2 子串回溯： j=1

BF算法时间复杂度

n为主串长度，m为子串长度，最坏情况比较了 (n-m+1)*m 次，若m<<n,算法复杂度为 O(n*m)

函数说明

进行循环，循环次数为子串长度，若字符不匹配则重新开始循环。 循环跳出的条件为：在进行第子串长度T.length次字符匹配后，若第T.length依然与主串匹配，则控制条件++j可是while语句跳出循环。

测试代码

#include<stdio.h> typedef struct { char ch[100 + 1]; //存储串的一维数组 int length;//串的当前长度 }SString; int Index_BF(SString S, SString T) { int i = 1, j = 1;//i为从某个位置开始查找，可添加参数进行修改 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;//模式匹配不成功 } int main() { SString a = { " aaaaab",6 }; SString b = { " aaab",4 }; int n = Index_BF(a, b); printf("从主串第%d个字符开始匹配！", n); }

最终a返回的结果为3，说明主串从下标3起往后取子串长度个字符与子串相匹配，串通常第一个下标 [0] 不存储数据元素。