字符串匹配

Frey December 21, 2017 [算法] #C语言

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(i<n){
            if (j == 0 || r[i] == r[j]) {
                ++i; ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
    int KMP(char *s,int slen,char *r,int rlen){
        int *next=getnext(r,rlen);
        int i=1,j=1;
        while(i<=slen&&j<=rlen){
            while(j<=rlen&&s[i]==r[j]){
                i++;j++;
            }
            if(j>rlen){
                return i-j+1;
            }else{
                j=next[j];i++;
            }
        }
        return 0;
    }

参考文章

1.字符串匹配的KMP算法

Back to top