字符查找算法 BF算法

coderon 2021-08-31 原文

BF算法是一种很简单粗暴的方法，可谓是重复性的暴力破解。所以还会有更高级的KMP算法。

一、实现思想

　　首先说一下什么叫字符串查找算法，比如有一个字符串S = “abcd”、一个字符串T = “bcd”,寻找字符串T在字符串S中的位置的算法，就是字符串查找算法。

　　BF算法是比较简单粗暴的方法

　　让每一趟字串和主串比较的起点，是从主串的第一个位置到最后一个位置。(这里比较绕口，但也是KMP算法改进的地方)

二、实现图例

三、实现代码

 1 #include <stdio.h>
 2 int BF(char s[], char t[])
 3 {
 4     int start = 0; //主串开始匹配的起始下标
 5     int i = 0;     //比较过程主串的下标
 6     int j = 0;     //比较过程字串的下标
 7     while ((s[i] != \'\0\') && (t[j] != \'\0\'))
 8     {
 9         if (s[i] == t[j])
10         {
11             i++;
12             j++;
13         }
14         else
15         {
16             start++;
17             i = start;
18             j = 0;
19         }
20     }
21     if (t[j] == \'\0\')
22         return start;
23     else
24         return -1;
25 }
26 int main(void)
27 {
28     char s[] = "ababaababcb";
29     char t[] = "ababc";
30     int location = BF(s, t);
31     if (location == -1)
32         printf("not found\n");
33     else
34     {
35         printf("loacation = %d\n", location);
36         for (int i = 0; i < 6; i++)
37         {
38             printf("%c", s[location]);
39             location++;
40         }
41     }
42 
43     return 0;
44 }
45 /* 
46 输出：
47 ——————————
48 loacation = 5
49 ababcb
50 ——————————
51  */

四、总结

　　我是先自己写了一遍BF算法，然后再看书上的(我得课本是王红梅的数据结构，上面那段BF代码就是复制这里的)，发现书本上的比我的简洁，后来我又在网上看到一段代码，发现更简洁。我发现代码要写得够简洁，对算法本身要有生动形象的理解，甚至脑海里会有算法执行的动画，那些关键的地方总是会在脑海里出现。对算法本身熟悉以后，会发现有很多变量可以重用哦，不用重新定义。这真的是又刷新我的观念了。

int BF_2(char s[], int len1, char t[], int len2)
{
    int i = 0; //i、j分别用于S和T得小标移动位置
    int j = 0;
    for (int k = 0; k < len1 - len2; k++)
    {
        i = k;
        for (int h = 0; h < len2; h++)
        {
            if (s[i] == t[j])
            {
                i++;
                j++;
            }
            else
                break;
        }
        if (j == len2)
            return k;
        else
            j = 0;
    }
    return -1;
}

我的BF

int BF_3(char s[], char t[])
{
    int len1 = strlen(s);
    int len2 = strlen(t);
    for (int i = 0; i < len1 - len2; i++)
    {
        int k;
        for (k = 0; k < len2; k++)
        {
            if (s[i + k] != t[k])
                break;
        }

        if (k == len2)
            return i;
    }
    return -1;
}