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; /*串的实际长度 */
} SString
/*在主串 s中定位查找子串 t的 BF模式匹配算法 */
int BFIndex (SString s,SString t)
{/*i,j为串数组的指针，分别指示主串 s和子串 t当前待比较的字符位置
*/
int i,j,v ;
i=0; /*主串指针初始化 */
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 (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的当前比较字符位置匹配过程：
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[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’=‘tj-
ktj-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; /*串的实际长度 */
} SString
/*数组 Next为全局变量 */
int Next[MAXSTRLEN]
/*在主串 s中定位查找子串 t的 KMP算法 */
int KMPIndex ( SString s,SString t)
{ int i,j,v ;
i =0; /*主串指针初始化 */
j = 0; /*子串指针初始化 */
while (i < s.len && j < t.len )
{
/*主串和子串的指针值各增加 1*/
if ( j == -1|| s.ch_string[i] == t.ch_string[j]
{
i ++;
j ++;
}
/*主串指针 i不回退，子串指针 j回退至 Next[j]*/
else
j = Next[j];
}
if ( j>= t.len )
v = i-t.len;/*v指向匹配成功的第一个字符 */
else
v = -1; /*模式匹配不成功 */
return (v);
}
求 next[j]
(1)当 j = 0 时，根据 next[j]的定义可以得知，
next[j]= -1
(2)设存在 next[j] = k，即在模式串 t中存在‘ t0
t1…t k-1’=‘tj-k tj-k+1…t j-1’（ 0<k<j）,k是满足‘ t0
t1…t k-1’=‘tj-k tj-k+1…t j-1’等式的最大值,求 next[j+1]
的值分以下两种情况,
如果 tk=tj,则 next[j+1] =next[j] + 1=k+1
如果 tk !=tj,则 next[j+1] = k’+1=next[k] + 1
事例：求 t=‘aaab’的 next[j]值求解过程如下：
当 j = 0时,next[0] = -1
当 j = 1时,next[1] = 0
当 j = 2时，有 t0=t1 =‘a’，所以有 next[2] = 1
当 j = 3时，有 t0t1 = t1t2 =‘aa’，所以有 next[3] = 2
即有
next[j]的算法
#define MAXSTRLEN 256 /*定义串允许的最大字符个数 */
struct string
{
char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度 */
int len; /*串的实际长度 */
} SString
/*数组 Next为全局变量 */
int Next[MAXSTRLEN]
/*求模式串 t的 next值。所求值存于全局变量 Next数组中 */
void GetNext (SString t)
{ int j,k ;
/*指针初始化 */
k = -1 ;
j = 0 ;
Next[0] = -1 ;
while (j < t.len –1 )
{
if (k == -1 || t.ch_string[j] ==t.ch_string[k] )
{
j ++ ;
k ++;
Next [j] = k ;
}
else
k = Next[k];
}
}