Osheep

时光不回头,当下最重要。

字符串匹配:BF算法

(一)算法原理

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

举例说明
S: ababcababa
P: ababa

BF算法的匹配步骤如下:

i=0, j=0 i=1, j=1 i=2,j=2 i=3, j=3 i=4, j=4(失败)
ababcababa ababcababa ababcababa ababcababa ababcababa
ababa ababa ababa ababa ababa
i=1,j=0(失败)
ababcababa
ababa
i=2,j=0 i=3,j=1 i=4,j=2(失败)
ababcababa ababcababa ababcababa
ababa  ababa  ababa
i=3,j=0(失败)
ababcababa
  ababa
i=4,j=0(失败)
ababcababa
  ababa
i=5,j=0 i=6,j=1 i=7,j=2 i=8,j=3 i=9,j=4(成功)
ababcababa ababcababa ababcababa ababcababa ababcababa
   ababa    ababa    ababa    ababa     ababa

(二)代码实现

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

int BFMatch(char *s,char *p)
{
    int i,j;
    i = 0;
    while(i < strlen(s))
    {
        j = 0;
        while(s[i] == p[j] && j<strlen(p))
        {
            i++;
            j++;
        }
        
        if(strlen(p) == j)
        {
            return i - strlen(p);
        }
        
        i = i - j + 1;                // 指针i回溯
    }
    
    return -1;
}

int main()
{
    char *szSource = "ababcababa";
    char *szSub = "ababa";
    int index = BFMatch(szSource, szSub);
    printf("目标串包含匹配串的起始位置:%d", index);
}

运行结果

目标串包含匹配串的起始位置:5

运算过程分析:
(1)
i=0, j=0, s[0]==p[0];
i=1,j=1, s[1]==p[1];
i=2,j=2, s[2]==p[2];
i=3,j=3, s[3]==p[3];
i=4,j=4, s[[4]!=p[4], 第一次循环结束,i=4-4+1=1

(2)
i=1, j=0, s[1]!=p[0], 第二次循环结束, i=1-0+1=2

(3)
i=2, j=0, s[2]==p[0];
i=3, j=1, s[3]==p[1];
i=4, j=2, s[4]!=p[2]; 第三次循环结束,i=4-2+1=3

(4)
i=3, j=0, s[3]!=p[0]; 第四次循环结束,i=3-0+1=4

(5)
i=4, j=0, s[4]!=p[0]; 第四次循环结束,i=4-0+1=5

(6)
i=5, j=0, s[5]==p[0];
i=6, j=1; s[6]==p[1];
i=7, j=2, s[7]==p[2];
i=8, j=3, s[8]==p[3];
i=9, j=4, s[9]==p[4];
i=10, j=5, j==strlen(p), 最后一次循环结束,返回i-strlen(p) = 5

点赞