字符串匹配之BF算法

算法原理

BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串T的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较T的第二个字符和P的第二个字符；若不相等，则比较T的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。
BF算法是一种蛮力算法。

举例说明：通过C语言实现，找出字符串P第一次出现在字符串T中的位置索引

T:  abcbcabab

P:  aba

• BF算法的比较过程，我们通过下面的表格展示我们比较的过程

*为占位符 Y表示匹配 N表示不相等√表示匹配成功 i为字符串T的索引 j为字符串P的索引

i=0;j=0(Y)	i=1;j=1(Y)	i=2;j=2(N)
abcbcabab	abcbcabab	abcbcabab
aba	aba	aba

i=1;j=0(N)
abcbcabab
*aba

i=2;j=0(N)
abcbcabab
**aba

i=3;j=0(N)
abcbcabab
***aba

i=4;j=0(N)
abcbcabab
****aba

i=5;j=0(Y)	i=5;j=1(Y)	i=5;j=2(√)
abcbcabab	abcbcabab	abcbcabab
*****aba	*****aba	*****aba

从上面的实现过程，我们不难发现，通过BF算法最坏的的情况下，我们可能需要比较(10-3)*3次才能完成最后的结果

• 代码实现

#include <stdio.h>
#include <string.h>

size_t stringLength(const char *str);//函数声明
int rangeOfString(const char * P, const char * T);//函数声明

int main(int argc, const char * argv[]) {
    
    //定义目标字符串P和模式字符串T
    char *P = "abcbcabab";
    char *T = "aba";
    printf("字符串T在字符串P中第一次出现的索引:%d\n", rangeOfString(P, T));
    return rangeOfString(P, T);
}

int rangeOfString(const char * P, const char * T) {
    //计算字符串P和T的长度，需要引用#include <string.h>文件
    //也可以通过stringOfLength（P）自定义方法获取字符串长度
    int pLength = (int)strlen(P);
    int TLength = (int)strlen(T);
    printf("字符串P的长度：%d\n", pLength);
    printf("字符串T的长度：%d\n", TLength);
    int i,j;
    i = 0;
    while (i < pLength) {
        j = 0;
        while (P[i] == T[j] && j < TLength) {
            i++;
            j ++;
        }
        if (j == TLength) {
            return (i - TLength);
        }
        i = i - j +1;
    }
    return i;
}

size_t stringOfLength(const char *str){
    unsigned long length = 0;
    while (*str++!=NULL) {
        length ++;
    }
    return length;
}