字符串匹配
1.BM
从左到右依次比较
s:主串
r:模式串
int BM(char *s,int slen,char *r,int rlen){
int i=1,j=1;
while(i<=slen-rlen+1){
while(j<=rlen&&s[i]==r[j]){
i++;j++;
}
if(j>rlen){
return i-j+1;
}else{
j=1;i++;
}
}
return 0;
}
2.KMP算法
通过一个next数字
当每次发生不匹配的时候
模式串不必回到开头
int* getnext(char *r, int n) { //next数组求解
int i, j;
int *next = (int *)malloc((n + 1) * sizeof(int));
next[0] = n; next[1] = 0;
j = 0;
i=1;
while(irlen){
return i-j+1;
}else{
j=next[j];i++;
}
}
return 0;
}