BF与KMP算法的写法与计算其遍历次数

BF和KMP算法

BF相当于一种暴力枚举，是手中没有地图的旅客
而KMP则会是手中有地图，看地图走的旅客

1. 效率分析

给定主串和模式串，分别统计模式匹配的BF算法和KMP算法的比较次数。
如主串为S=aaaaaaaaaa ,模式串为T=aaaab

BF比较次数为 34
KMP比较次数为 16
如主串为S=cdbbacc ,模式串为T=abcd
BF比较次数为 8
KMP比较次数为 8
KMP这个算法，理解了以后你会发现，都是脑子，为啥这么不同呢

🌚🌚🌚

2.BF代码

int  BF(string A, string B) 
{	int i =0, j = 0,count=0;	
while (i < A.length() && j < B.length()) 
{            count++;	
	//两个字符串均为比较到串尾（只有有一个到串尾就跳出循环）	
		if (A[i] == B[j])
		 {			i++;	
		 		j++;		}	
		 	else {			//匹配失败指针回溯	
		 			i = i - j + 1;	
		 					j = 0;		}	
		 	}	return count;
		 		/*if (j >= B.length()) return i - B.length();
		 			else return count;*/
		 			}

BF原理很简单,就是对主串的每一个字母为开头，与子串比较，如果相等，则匹配成功，而作为这个开头的就是上面代码中的i，作为子串开头的，就是这个j
i永不回溯，而j一但匹配失败，则回溯到子串首字母
KMP代码

int KMP(string str,string p)
{   
 int count = 0;
    int k=-1,j=0,next[p.length()];
    next[0]= -1;
     while(j<p.length())
         if(k==-1||p[j]==p[k])
             next[++j] = ++k;
         else k=next[k];

            int q=0,e=0;
    while(q<str.length()&&e<p.length())
    {      count++;
        if(q==-1||p[e]==str[q])
        {
            e++;
            q++;
        }
        else
        {
            e=next[e];
        }
    }
    return count;

}

KMP算法，总体可分为两步

1. 找到地图
2. 按地图走路

而这两部最核心的自然就是找到地图，即next数组

next数组怎么找呢，代码如下
next数组代码

    int k=-1,j=0,next[p.length()];
    next[0]= -1;
     while(j<p.length())如果未满
         if(k==-1||p[j]==p[k])
             next[++j] = ++k;
         else k=next[k];

这个就相当于子串回溯后的位置
什么意思呢，上面不是说到BF算法是j回溯到子串头部，而这个就相当于看地图走的那条捷径，前提是有捷径了话，即在子串有最大前后缀数时，j不再用回溯到头部，而是根据这个next数组走。

而很多人看不懂这个k=next[k]

         else k=next[k]; 

这里相当于递归，找到现在k个最大前后缀中的最大前后缀，如果一直没有，那么这个将会回到k=-1，即子串头部
以及

  next[++j] = ++k; 

这里的插入位置有必要说明
next[++j] = ++k; 计算的k永远是j上一位的最大前后缀数，而这里的k存到j位置。

这和匹配机制有关，即匹配失败时，看的应该是当前位置的上一级的相同前缀，匹配位置永远是后缀
所以找前缀

然后就是看地图去走

  int q=0,e=0;  
    while(q<str.length()&&e<p.length()) 
       {   
            if(q==-1||p[e]==str[q])   
                 {     e++;   
                         q++;   
                               }      
                                 else  
                                    e=next[e];    
                                    }
                                          }
  

 if(q==-1||p[e]==str[q]) 

即当子串指针在头部或者与主串相等

    e=next[e];  

即看地图找路

是不是恍然大悟？😏

如果想看BF或者kmp是否匹配成功，只需要对他们的主串指针和子串指针操作就行啦
也就是看是主串遍历完(失败)还是子串遍历完(成功)

如果想计算次数，那么加一个计数器就好啦

int count=0;

主函数

       int main(){  
             string str,p; 
                cin>>str>>p;   
                cout<<"BF:"<<BF(str,p)<<endl;    cout<<"KMP:"<<KMP(str,p)<<endl;}

这里就是简单的调用

完整代码

#include<bits×dc++.h>
using namespace std;
int BF(string A, string B) {
	int i =0, j = 0,count=0;
	while (i < A.length() && j < B.length()) {
            count++;
		//两个字符串均为比较到串尾（只有有一个到串尾就跳出循环）
		if (A[i] == B[j]) {
			i++;
			j++;

		}
		else {
			//匹配失败指针回溯
			i = i - j + 1;
			j = 0;
		}

	}
	return count;
	/*if (j >= B.length()) return i - B.length();
	else return count;*/
}
int KMP(string str,string p)
{    int count = 0;
    int k=-1,j=0,next[p.length()];
    next[0]= -1;
     while(j<p.length())
         if(k==-1||p[j]==p[k])
             next[++j] = ++k;
         else k=next[k];

            int q=0,e=0;
    while(q<str.length()&&e<p.length())
    {      count++;
        if(q==-1||p[e]==str[q])
        {
            e++;
            q++;
        }
        else
        {
            e=next[e];
        }
    }
    return count;

}
int main()
{
    string str,p;
    cin>>str>>p;
   cout<<"BF:"<<BF(str,p)<<endl;
    cout<<"KMP:"<<KMP(str,p)<<endl;

}

有事请@王也枉不了