算法—字符串匹配BF算法

有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T 式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母。

BF算法-爆发匹配算法

匹配模拟图

思路:

1. 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为0;
2. 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:

• S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
• 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 1)起再重新和模式第一个字符(j = 0)比较;

3. 如果j >= T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回-1;

时间复杂度：O(n*m)

BF模拟1!
接下来开始主串S和 模式串T的index 回溯对比
BF模拟2，3，4，5，6
如此循环。

int Index_BF1(char *S, char *T,int pos) {
    
    if (S == NULL || T == NULL) {
        return -1;
    }
    
    int lenS = (int)strlen(S);
    int lenT = (int)strlen(T);
    
    if (lenT < 1 || lenS < 1 || lenS < lenT) {
        return -1;
    }
    
    int i = pos;//i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配
    int j = 0;
    
    while (i < lenS && j < lenT) {
        if (S[i] == T[j]) {
            I++;
            j++;
        } else {//不相等,则指针后退重新匹配
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= lenT) {//找到了匹配
        return i - lenT + 1;
    }
    return -1;
}

int main(int argc, const char * argv[]) {
    char *S = "abcdex";
    char *T = "bc";

    i = Index_BF1(S, T, -1);

    if (i == -1) {
       printf("没有找到匹配的模式串\n");
    } else {
        printf("匹配到了，从第i = %d个元素开始\n",i);
    }
    
    return 0;
}

BF算法效率分析：

案例图
碰到上图的案例，BF算法就会进行超多的判断操作，效率比较低下。
但BF算法能比较快速的解决算法问题，能够快速想到并完成。