字符串匹配算法 -- 朴素匹配

lexingsen

发布于 2022-02-24 07:44:55

1.9K00

代码可运行

文章被收录于专栏：乐行僧的博客乐行僧的博客

运行总次数：0

代码可运行

何为匹配? 就是在一个串中寻找是否和有何目标串相同的真字串。

为什么叫做朴素匹配，我理解的就是这是一种寻常想法，简单粗暴的算法。是一种暴力的算法，不考虑其时间复杂度以及效率。只要达到匹配的目的即可。

代码实现：

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

static int PuSu(const char* s,const char* sub,int pos)
{
    assert(s != NULL);
    assert(sub != NULL);
    int i = pos;//从主串的第pos个位置开始匹配
    int j = 0;//目标串
    int lens = strlen(s);
    int lensub = streln(sub);
    while(i < lens && j < lensub)
    {
        if(s[i] == sub[j])
        {
            i++;j++;
        }
        else
        {
            i = i - j + 1;//主串回溯
            j = 0;//目标串回退到下标为0
        }
    }
    if(j >= lensub) 
    {
        return i-j;
    }
    return -1;//返回`-1`以示未匹配到
}

测似：

int main()
{
    char* s = "abcdabad";
    char* sub = "aba";//可以看出，在主串的第四个位置可以匹配到 下标从0开始
    int n = PuSu(s,sub,0);
    printf("n = %d\n",n);
    return 0;
}