54.1模式匹配的BF算法 算法思想:s中的第一个字符与t中的第一个字符 进行比较,若不同,就将S中的第二个字符与t 的第一个字符进行比较.,直到s的某一个字符 和t的第一个字符相同;再将它们之后的字符进行 比较,若也相同,则如此继续往下比较;依此类 推,重复上述过程。最后,会出现两种情况: (1)在中找到和t相同的子串,则匹配成功 (2)将s的所有字符都检测完了,找不到与t相 同的子串,则匹配失败
5.4.1 模式匹配的BF算法 算法思想：s中的第一个字符与t中的第一个字符 进行比较，若不同，就将s 中的第二个字符与t中 的第一个字符进行比较……，直到s的某一个字符 和t的第一个字符相同；再将它们之后的字符进行 比较，若也相同，则如此继续往下比较；依此类 推，重复上述过程。最后，会出现两种情况： (1) 在s中找到和t相同的子串，则匹配成功 (2)将s的所有字符都检测完了，找不到与t相 同的子串，则匹配失败
算法: define maXstrlen 256 定义串允许的最大字符个数 struct string char ch string MAXSTRLEN];/ MAXSTRLEN为串的最大长度 int len: /*串的实际长度 3 SString /在主串s中定位查找子串t的BF模式匹配算法 int BFIndex(sString s, SString t) {*i为串数组的指针,分别指示主串s和子串t当前待比较的字符位置 inti, J,v; i=0;/主串指针初始化 j=0;/子串指针初始化*
算法： #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/ struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度 */ int len; /*串的实际长度*/ } SString /*在主串s中定位查找子串t的BF模式匹配算法*/ int BFIndex (SString s, SString t) {/*i,j为串数组的指针，分别指示主串s和子串t当前待比较的字符位置 */ int i, j,v ; i=0; /*主串指针初始化*/ j=0; /*子串指针初始化*/
while(i<slen &&j< t len) if(sch string []=t ch string 0]) 继续匹配下一个字符+ +十 else 主串和子串指针回退重新开始下一次匹配* ⅰ=i-j+1;/新一轮匹配开始,t对应的s的开 始比较位置* )j=0;/从子串的第一个字符进行新匹配*
while (i < s.len && j< t.len ) { if ( s.ch_string [i] =t.ch_string [j] ) { /*继续匹配下一个字符*/ i++; j++; } else { /*主串和子串指针回退重新开始下一次匹配*/ i=i-j+1 ; /*新一轮匹配开始，t0对应的s的开 始比较位置*/ j=0 ; /*从子串的第一个字符进行新匹配*/ } }
if (i>=t len V=i- t len;/v指向匹配成功的第一个字符 else V=-1;/模式匹配不成功* eturn(v) 时间复杂度:On×m) 事例:设目标串s= addada,模式串tada'。s 的长度为n(n=6),t的长度为m(m=3):用指针i 指示目标串s的当前比较字符位置,用指针指 示模式串t的当前比较字符位置
if (j >= t.len ) v = i – t .len ; /*v指向匹配成功的第一个字符*/ else v = -1 ; /*模式匹配不成功*/ return (v); } 时间复杂度：O(n×m) 事例：设目标串s=‘addada’，模式串t=‘ada’。s 的长度为n(n=6)，t的长度为m(m=3)；用指针i 指示目标串s的当前比较字符位置，用指针j指 示模式串t的当前比较字符位置
匹配过程: s add ad a dd ada (a)第一趟匹配s=t2 (b)第二趟匹配s1=t i=2 s addada s ad dada a d a (c)第三超匹配a2=to (④)第四趟匹配成功 图55模式匹配过程
匹配过程：