Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

字符串匹配算法---BF

_程序兔 2019-10-07 13:30:00 阅读数:669 评论数:0 点赞数:0 收藏数:0

Brute-Force算法,简称BF算法,是一种简单朴素的模式匹配算法,常用语在一个主串string 内查找一个子串 pattern的出现位置。

核心思想:

  i 遍历主串string

    i 每自增一次,内层循环用 j 遍历子串 pattern ,同时判断 patter[j] == string[i+j]

      若条件成立,j 自增

         否则退出循环

    判断 j 是否遍历到 pattern尾部

      若 j == strlen(pattern),匹配成功,return i;

      若 j != strlen(pattern), 匹配失败 , i 自增继续从str的下一个字符一个一个匹配。

  i 遍历完主串string程序仍没有结束,说明没有找到子串pattern,return -1 

比如要在stringaaacaaab中查找patternaaab:

代码实现:

int BF(char pattern[], char str[])
{
    for(int i = ; i < strlen(str); ++i){ // i遍历主串str
        int j;
        for(j = ; pattern[j] && str[i+j] == pattern[j]; ++j); // j遍历子串pattern,pattern[j] != str[i+j]时结束循环
        if(!pattern[j]){ // j匹配至pattern尾部,匹配成功
            return i;
        }
    }
    return -;
}

 

版权声明
本文为[_程序兔]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/GuoYuying/p/11630139.html