数据结构字符串模式匹配算法之BF算法(使用纯C程序描述)

//字符串匹配过程如图所示,故不再叙述;

//本程序是可移植性程序;

//能在Linux/Mac os/Windows下编译运行;

//若有不足之处请提出，博主会尽所能修改;

//若是对您有用的话请点赞或分享提供给它人;

//未经允许严禁抄袭以及转载;

//源代码奉上,希望能够对您有所启发;

//brute_force.c

#include <stdio.h>
#include <string.h>
#define LEN 20

char *s_gets(char *st, int n);
int brute_force(const char *s, const char *t, int pos);

int main(int argc, char *argv[])
{
    int n;
    char str1[LEN];
    char str2[LEN];

    printf("本程序采用BF模式匹配算法判断子串是否处于主串中\n");
    printf("请输入主串(换行结束输入):\n");
    while (s_gets(str1, LEN) && *str1 != '\0')
    {
        printf("请输入子串:\n");
        if (s_gets(str2, LEN) && *str2 != '\0')
        {
            n = brute_force(str1, str2, 0); //从起始字符开始匹配,可任意决定匹配位置;
            if (n != -1)
            {
                printf("子串%s在主串%s中, 子串出现于主串第%d个位置\n", str2, str1, n);
            }
            else
            {
                printf("子串%s不在主串%s中\n", str2, str1);
            }
            printf("您可以再次输入2串字符串(或换行退出):\n");
        }
    }
    printf("本程序完成!\n");

    return 0;
}

char *s_gets(char *st, int n) //这是一个字符串输入函数,防止内存泄漏;
{
    char *ret_val;
    char *find;

    ret_val = fgets(st, n, stdin);
    if (ret_val)
    {
        find = strchr(st, '\n');
        if (find)
        {
            *find = '\0';
        }
        else
        {
            while (getchar() != '\n')
                continue;
        }
    }
    return ret_val;
}

int brute_force(const char *s, const char *t, int pos)
{
    int i = pos;             //主串从第pos个位置开始匹配;
    int j = 0;               //子串从第一个字符开始匹配;
    int slength = strlen(s); //获取主串长度;
    int tlength = strlen(t); //获取子串长度;

    while (i < slength && j < tlength)
    {
        if (s[i] == t[j]) //若主串字符与子串字符匹配;
        {
            ++i; //则进行下一个字符匹配;
            ++j;
        }
        else //若是不匹配;
        {
            i = i - j + 1; //则主串计数器i回溯到上一次匹配字符的下一个字符;
            j = 0;         //子串从头开始匹配;
        }
    }
    if (j >= tlength) //若子串计数器j大于或等于子串长度说明匹配成功;
    {
        return i - tlength + 1; //返回子串第一个字符出现在主串的位置;
    }
    else
    {
        return -1; //若计数器j小于子串长度说明匹配失败,返回-1;
    }
}

//---------------------------------------------------------;

//-------------------------------------------------2020年6月15日-------------------------------------------------------;