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;

}

有事請@王也枉不了