欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

朴素匹配

程序员文章站 2024-03-17 17:49:04
...
        ## **朴素匹配** ##

何为朴素匹配?
朴素匹配其实就是我们所熟知的暴力匹配,简单的说,就是对主串进行遍历,与匹配串每一个字符进行匹配,如果对应的字符不相等,主串后移,匹配串不动;
匹配过程中如果相等,两个串同时向后移,如果将匹配串全部遍历,则说明找到了,返回 主串现在位置减去字串长度;
匹配过程中如果不相等,则将主串返回到匹配到的下一个位置,匹配串返回到开始的位置,然后继续往后匹配,直到主串全部遍历。

理论是不是很绕呀,让我用图来为大家解释一下吧!

1,主串str 第一位开始,前二个字母都匹配成功
但str的第三位是c,而sub的第三位是a,匹配失败,
竖线表示相等,X表示不相等。
朴素匹配
2,主串str第二位开始,主串str的首字母为b,匹配串sub的首字母是a,匹配失败。
朴素匹配
3,主串str第三位开始,主串str首字母为c,匹配串sub的首字母为a,匹配失败。
朴素匹配
4,主串第四位开始,主串str与匹配串sub三个字母全部匹配完,匹配成功。
朴素匹配

这就是朴素匹配,就是对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做sub长度的小循环,直到匹配成功或全部遍历。

接下来让我用代码展示一下朴素匹配:

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

int BF(const char *str, const char *sub)
{
    assert(str != NULL && sub != NULL);
    int i = 0; //主串下标
    int j = 0; //匹配串下标
    int str_len = strlen(str);//主串长度
    int sub_len = strlen(sub);//匹配串长度
    if(sub_len > str_len || sub_len == 0)
        return -1;  //匹配串大于主串,无法匹配
    while(i < str_len && j < sub_len)
    {
        if(str[i] == sub[j]) //相等同时后移
        {
            i++;
            j++;
        }
        else //不相等
        {
            i = i - j + 1;//主串回溯到字串的下一个位置
            j = 0; //匹配串回到起始位置
        }
    }
    if(j >= sub_len)    
    {
        return i - j; //匹配成功  返回主串相应的位置
    } 
    return -1; //失败返回-1
}

int main()
{
    char *str = "abcabac";
    char *sub = "aba";
    int m = BF(str,sub);
    printf("%d\n",m);    
    return 0;
}

朴素匹配

该朴素匹配函数返回的是匹配成功或主串的下标,失败返回-1.

相关标签: 字符串匹配