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模式匹配过程
匹配过程：
542模式匹配的KMP算法 KMP算法的基本思想:设s为目标串,t为模式 串,设指针利指针分别指示目标串和模式串中正 待比较的字符,开始时,令i=0,j=0。如果s 则使i的值分别增加1;反之,i变,j的值 退回到=next的位置(即模式串右滑),然后 再对s和进行比较。依次类推,直到出现下列两 种情况之一: (1)j值退回到某个nex时,有s=t,则指 针的值各增加1后,再继续匹配; (2)道退回到=-1,此时令指针的值各增加1, 也即下一次对s和0进行比较
5.4.2 模式匹配的KMP算法 KMP算法的基本思想：设s为目标串，t为模式 串，设i指针和j指针分别指示目标串和模式串中正 待比较的字符，开始时，令i = 0，j = 0。如果si= tj，则使i和j的值分别增加1；反之，i不变，j的值 退回到j = next[j]的位置（即模式串右滑），然后 再对si和tj进行比较。依次类推，直到出现下列两 种情况之一： （1）j值退回到某个j=next[j]时，有si= tj，则指 针的值各增加1后，再继续匹配； （2）j值退回到j=-1，此时令指针的值各增加1， 也即下一次对si+1和t0进行比较
函数next]: (1)当存在‘tot1.k-1=-kt-k+1.j-1(0<kj) 时:nex切=maxk0<k<j且“tot1.+k-1= t-k+1.!-1} (2)当=0时,next=-1 其他情况,next]=0
函数next[j]： (1) 当存在 ‘t0 t1…tk-1’=‘tj-ktj-k+1…tj-1’ (0<k<j) 时：next[j] = max{k|0< k < j且‘t0 t1…tk-1’=‘tjktj-k+1…tj-1’ } (2) 当j = 0时，next[j] = -1 其他情况， next[j] = 0
KMP模式匹配算法 define maxstrlen 256 /定义串允许的最大字 符个数 struct string char ch_ string MAXSTRLEN];/ MAXSTRLEN为串 的最大长度* int len: /串的实际长度* 3 SString 广数组Next为全局变量 int Next[MAXSTRLEN /在主串s中定位查找子串t的KMP算法 int KMPIndex( SString s, SString t) i int i,j i=0;阵主串指针初始化 j=0;/子串指针初始化
KMP模式匹配算法 #define MAXSTRLEN 256 /*定义串允许的最大字 符个数*/ struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串 的最大长度*/ int len; /*串的实际长度*/ } SString /*数组Next为全局变量*/ int Next[MAXSTRLEN] /*在主串s中定位查找子串t的KMP算法*/ int KMPIndex ( SString s, SString t) { int i, j, v ; i =0; /*主串指针初始化*/ j = 0; /*子串指针初始化*/
while(i<slen &&j<tlen /主串和子串的指针值各增加1 if(j==-1sch string[]=t ch string] ++; ++ /主串指针不回退,子串指针回退至Nex else j=Next[]; if (j=t len V=i-len;/v指向匹配成功的第一个字符 else ⅴ=-1;芦模式匹配不成功 return (v)
while (i = t.len ) v = i-t.len;/*v指向匹配成功的第一个字符*/ else v = -1; /*模式匹配不成功*/ return (v); }
求 nextp (1)当=0时,根据nex切的定义可以得知, next]=-1 (2)设存在nex=k,即在模式串坤存在“t t1…t1=水k+1…+1(0k灯j),k是满足 t1…求=!水k+1…+1等式的最大值,求nex+1 的值分以下两种情况: 如果t=,则next+1=nex1]+1=k+1 如果t!=t,则next+1]=K+1= next(k]+1
求next[j] (1)当j = 0 时，根据next[j]的定义可以得知， next[j]= -1 (2)设存在next[j] = k，即在模式串t中存在‘t0 t1…tk-1 ’=‘tj-k t j-k+1…tj-1 ’（0<k<j），k是满足‘t0 t1…tk-1 ’=‘tj-k t j-k+1…tj-1 ’等式的最大值,求next[j+1] 的值分以下两种情况： 如果tk=tj ，则next[j+1] =next[j] + 1=k+1 如果tk !=tj ，则next[j+1] = k’+1=next[k] + 1
