首页 > 代码库 > 判断一个字符串中是否包含另一个字符串（KMP、BF）
判断一个字符串中是否包含另一个字符串（KMP、BF）
判断一个字符串是否是另一个字符串的子串，也就是strstr（）函数的实现，简单的实现方法是BF算法。
1.BF算法
int BF(char *s, char *p){ if(s==NULL || p==NULL)return -1; int i=0; int j; while(i<strlen(s)){ j=0; while(s[i]==p[j] && j<strlen(p)){ i++; j++; } if(j==strlen(p))return i-j; i=i-j+1; } return -1;}
2.KMP算法
KMP算法的原理有很多文章解释，这就不说了（我也看得不是很懂......）。整个KMP算法的关键点在于next数组的实现。
KMP算法主体：
int KMP(char *s, char *p){ if(s==NULL || p==NULL)return -1; int next[100]; get_next(next, p); int i=0; int j=0; while(i<strlen(s)){ if(j==-1 || s[i]==p[j]){ i++; j++; }else{ j=next[j]; } if(j==strlen(p))return i-j; } return -1;}
get_next函数的实现：
void get_next(int *next, char *p){ if(next==NULL || p=NULL)return; int i=0; int j=-1; next[0]=-1; while(i<strlen(p)-1){ if(j==-1 || p[i]==p[j]){ i++; j++; next[i]=j; }elseP{ j=next[j]; } }}
注意，get_next函数的实现只与子字符串有关系...
判断一个字符串中是否包含另一个字符串（KMP、BF）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。