4.3.3 串的模式匹配算法
- 【算法目的】确定主串中所含子串（模式串）第一次出现的位置（定位）
- 【算法种类】
- BF算法
- KMP 算法
BF 算法
Brute-Force简称为BF算法，亦称为简单匹配算法。采用穷举法的思路
例如，设目标串S="aaaaaab"，模式串T="aaab"。S的长度为n(n=6),T的长度为m(m=4)。
BF算法的匹配算法如下：
这里是有动画，但是动画不知道怎么上传所以无法显示。这里动画内容就是暴力破解法相关过程。
当匹配成功时，返回结果是i-t.length
Index(S,T,pos)
-
将主串的第pos个字符和模式串的第一个字符比较
-
若相等，继续逐个比较后续字符
-
若不等，从主串的下一个字符起，重新与模式串的第一个字符比较。
- 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
- 否则，匹配失败，返回值为0
-
【算法描述】
int Index_BF(SString S,SString T){
// 首先是判断主串和子串是否为空
if(S""||T""){
return ERROR;
}// 创建变量 int i=0,j=0; // 也就相当于两个指针变量 // 开始循环判断,循环结束的标志就是两个指针其中某一个指针指向空（可以说是指针越界） while(i<=S.length&&j<=T.length){ /* 如果说两个指针的元素相等，将两个指针向后移动一位 如果说两个指针的元素不相等，就进行回溯。 */ if(S.ch[i]==T.ch[j]){ // 如果说两者相等的情况下 ++i;++j; // 两个指针向后进行移动 }else{ // 否则 i=i-j+2; // i 进行回溯，为啥还需要+2 指针指向的数组的基地址 // 而且我们是需要跳过首位元素 所以需要加上2 j=1; } // 这里是结束条件的判断 if(j>=T.length){ return i-T.length; }else{ return 0; } } } // 将这个函数进行重载 int Index_BF(SString S,SString T,int pos[]){ // 首先是判断主串和子串是否为空 if(S==""||T==""){ return ERROR; } // 创建变量 int i=pos,j=0; // 也就相当于两个指针变量 // 开始循环判断,循环结束的标志就是两个指针其中某一个指针指向空（可以说是指针越界） 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; } } }
若n为主串的长度，m为子串长度，最坏的情况是
- 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次
- 最后m位也各比较了1次
总次数为:(n-m)* m+m=(n-m+1)* m
若m<<n,则算法复杂度为O(n*m)
KMP 算法
该算法较BF算法有较大改进，从而使算法效率有了某种程度的提高
利用已经部分匹配的结果而加快模式串的滑动速度？
且主串S的指针i不必回溯，可将时间复杂度提高到O(n+m)
为此，定义next[j]函数，表明当模式中第j个字符与主串中相应字符"失配"时，在模式中需重新和主串中该字符进行比较的字符位置。
上面的max函数所表达的意思是：前缀和后缀相等的情况下，最长的情况
咱们看下面的例子
这里是需要说明一下的是：每一位元素对应的next[]数组的值是指该（元素）字符前面的子串的最长前后缀相等的长度值。
如何求next[]
- 【算法思想】除当前字符外的最长相同前缀后缀。这里主要是先确定那个位置与首位字符相等，然后在此基础进行判断进行累加操作，不相等就将头部指针进行置0
- 【算法描述】
void get_next(SString T,int &next[]){
// 命名两个指针进行初始化
int j=0,i=-1;
// 首先是将第一位进行初始化操作。
next[0]=-1;
// 进入循环结构
while(j<T.length){
// 当i归置-1时或者说当两个指针指向字符相等时，将两个指针向后移动一位，进行累加判别。
if(i-1||T.ch[i]T.ch[j]){
++i;++j;
// 并且将j指针对应的next[]进行赋值。
next[j]=i
}else{
// 当两个指针指向的元素不相等时，那么这个将执行多次，以至于将i归置-1，但是这个时候j指针是不动的。
i=next[i];
}
}
}
KMP算法
- 【算法思想】通过上面的next[]数组获得模式串回溯的位置
- 【算法描述】
int Index_KMP(SString S,SString T,int pos){
// i指针是指向主串，j指针是指向模式串
int i=pos,j=1;
while(i<S.length&&j<T.length){
if(j0||S.ch[i]T.ch[j]){
++i;++j;
}else{
j=get_next[j];
}
}
if(j>T.length)
return i-T.length;
else
return 0;
}