当前位置:网站首页>Detailed explanation of BF and KMP
Detailed explanation of BF and KMP
2022-07-06 05:57:00 【Rhinoceros Superman】
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 :
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 .
边栏推荐
- 【LeetCode】Day96-第一个唯一字符&赎金信&字母异位词
- RustDesk 搭建一个自己的远程桌面中继服务器
- 【SQL server速成之路】——身份驗證及建立和管理用戶賬戶
- As3013 fire endurance test of cable distribution system
- LTE CSFB process
- The usage and difference between strlen and sizeof
- 养了只小猫咪
- Web Security (V) what is a session? Why do I need a session?
- ArcGIS application foundation 4 thematic map making
- B站刘二大人-线性回归及梯度下降
猜你喜欢
LAN communication process in the same network segment
RustDesk 搭建一个自己的远程桌面中继服务器
清除浮动的方式
[SQL Server fast track] - authentication and establishment and management of user accounts
Yygh-11-timing statistics
SequoiaDB湖仓一体分布式数据库2022.6月刊
Hongliao Technology: Liu qiangdong's "heavy hand"
Yunxiaoduo software internal test distribution test platform description document
Analysis of grammar elements in turtle Library
Huawei BFD configuration specification
随机推荐
Station B, Mr. Liu Er - multiple logistic regression, structure 7
H3C V7版本交换机配置IRF
PDK工藝庫安裝-CSMC
[experience] install Visio on win11
c语言——冒泡排序
【LeetCode】Day96-第一个唯一字符&赎金信&字母异位词
请求转发与重定向
[paper reading] nflowjs: synthetic negative data intensive anomaly detection based on robust learning
Download, install and use NVM of node, and related use of node and NRM
类和对象(一)this指针详解
C language bubble sort
Auto.js学习笔记17:基础监听事件和UI简单的点击事件操作
RustDesk 搭建一个自己的远程桌面中继服务器
High quality coding tool clion
P2802 go home
The difference and usage between continue and break
Memory and stack related concepts
Report on market depth analysis and future trend prediction of China's arsenic trioxide industry from 2022 to 2028
Anti shake and throttling are easy to understand
[Jiudu OJ 07] folding basket