Detailed explanation of BF and KMP

One 、BF Algorithm .

BF Pattern matching algorithm is easy to understand and program , But when the text is large , The response efficiency of the computer will be relatively low , So it is also called “ Violent match ”.

Implementation process ：

Initial diagram

 

When a matching position is required pos by 1 when ：

  If the elements are the same , be i++,j++ Match in turn , If it's not the same ：

Then put i The pointer goes back to 2 position ,j Move to... Of the pattern string 1 position , And then start the process again ：

 

 

As for the understanding of backtracking position , Individuals use mathematical induction ：

  Set at this time i=M=7,j=N=3   M-N Represents the previous item of the starting position of the starting match in the main string , So to produce effective backtracking , You have to M-N+2 , Take this as an example ,M-N+2=4+2=6  Just the last item of the starting position . 

 //BF matching 
int BF(HString s,int pos,HString t ){
	int i=pos,j=1;                      //i Understood as string s The variable of   j Understood as string t The variables in the 
	while(i<=s.len&&j<=t.len){         // When neither string reaches the end 
		if(s.ch[i]==t.ch[j]){          // If the string matches , Then traverse in turn 
			i++;
			j++; 
		}else{                      // If it doesn't match , Then go back 
			i=i-j+2;  // Backtracking position  
			j=1;
		} 
	}
	if(j>=t.len){                    // The final output 
		printf(" The starting position of the pattern string is ：%d",(i-t.len));
		return true;
	} else{
		return false;
	}
}

Two 、KMP Algorithm .

KMP Algorithm abbreviation “ No backtracking algorithm ”, Its important point is this next How to calculate the value , and next[1]=0,next[2]=1 This is unchanged , The rest next Value is simply to see whether the prefix and suffix of the previous string are equal .

1.next The calculation of the value

in the light of   " abaabcac " This string

 next [ 1]= 0,next [2]=1

Because there is no real child string , So the substring length is 0 so next [3] =1.

next [4] ,next [5] These two substrings are 1, Then both are 2

next [ 6] The substring is 2, so next [ 6]=3. And so on .  Final next The value is   0 1 1 2 2 3 1 2

2.nextval The calculation of the value .

nextval The value can be based on next Value to judge , General programming is not easy to use , It is often used for multiple-choice questions of data structures .

For example, as mentioned above character string s" abaabcac "         next [1-8] The value of is ：0 1 1 2 2 3 1 2

When j=1 when , Defined ：nextval[ 1]=0

When j=2 when ,next [2] =1, s2 It's not equal to s1 , be nextval [2] =next [2] =1

When j=3 when ,next [3] =1,  s3 be equal to s1 , be nextval [3] =nextval [3] =0

When j=4 when ,next [4] =2, s4 It's not equal to s2, be nextval [4] = next [4] =2

3、 ... and 、 Overall code implementation .

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define false 0
#define true 1
typedef struct {
	char *ch;    // A character array , If it is not empty, it points to the starting address , If it is empty, then NULL 
	int len;   // length  
}HString;
// initialization 
int HInit(HString *s){
	s->ch=NULL;
	s->len=0;
} 
// String assignment 
int HStrAssign(HString *s,const char *chars){
	int i=0;
	while(chars[i]!='\0'){    // Determine the string length  
		i++;
	}
	s->len=i;
	if(s->ch!=NULL){
		free(s);
	}else{
		s->ch=(char *)malloc((s->len+1)*sizeof(char));//0 Unit No 
		if(s==NULL){
			printf(" Space application failed ！");
			return false;
		} 
	for( i=1;i<=s->len;i++){   // Assign values in sequence  
		s->ch[i]=chars[i-1];
	}
	}
}
// String traversal 
int HSbianli(HString *s){
	if(s->len==0){
		printf(" String empty ！");
		return false; 
	}else{
		int i;
		for(i=1;i<=s->len;i++){
			printf("%c",s->ch[i]);
		}
		return true;
	}
}
 //BF matching 
int BF(HString s,int pos,HString t ){
	int i=pos,j=1;
	while(i<=s.len&&j<=t.len){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			i=i-j+2;  // Backtracking position  
			j=1;
		} 
	}
	if(j>=t.len){
		printf(" The starting position of the pattern string is ：%d",(i-t.len));
		return true;
	} else{
		return false;
	}
}
//KMP matching 
//---------------next Algorithm -----------------
void GetNext(HString s,int next[]){
	int j=1,k=0;
	next[1]=0;
	while(j<s.len){
		if(k==0||s.ch[j]==s.ch[k]){
			++j;++k;
			next[j]=k;
		}else{
			k=next[k];
		}
	}
   for(int j=1;j<=s.len;j++){
   	printf(" %d ",next[j]);
   }
}
//---------------nextval Algorithm -----------------
void GetNextval(HString s,int next[],int nextval[]){
 	int j=2,k=0;
 	printf("\n Pattern string next The value is ：");
	GetNext(s,next);
	nextval[1]=0;
	while(j<=s.len){
		k=next[j];
		if(s.ch[j]==s.ch[k]){
			nextval[j]=nextval[k];
		}else{
			nextval[j]=next[j];
			j++;
		} 
	}
	printf("\n Pattern string nextval The value is ：");
	for(int i=1;i<=s.len;i++){
		printf(" %d ",nextval[i]); 
	}	
}
//-------------------KMP------------------
int KMP(HString s,int pos,HString t,int next[]){
	int i=pos,j=1;
	while(i<=s.len&&j<=t.len){
		if(j==0||s.ch[i]==t.ch[j]){   // If it is the same, continue to compare the following characters  
			++i;++j;
		}else{
			j=next[j];                // The mode string slides to the right  
		}
		if(j>t.len){
			printf(" The starting position of the pattern string is ：%d",(i-t.len));   // The match is successful , Return to the starting position  
			return true;
		}
	}
}
int main(){
	HString s;
	HString s1;
	HInit(&s);
	HInit(&s1);
	char a[]={"ababcabcacbab"};
	char b[]=("abcac");
	HStrAssign(&s,a);
	HStrAssign(&s1,b);
	printf(" At this time, the matching string is :");
	HSbianli(&s);
	printf("\n At this time, the mode string is :"); 
	HSbianli(&s1);
	printf("\n Conduct BF matching ");
	BF(s,1,s1);
	int next[s1.len];
	int nextval[s1.len];
	GetNextval(s1,&next[s1.len],&next[s1.len]);
	printf("\n Conduct KMP matching ");
	KMP(s,1,s1,&next[s1.len]);
} 

result ：

Tested , Can run , To change data, just change char a[ ] and char b[ ] Just do it .