字符串查找BF算法

BF(Brute Force)算法为暴力匹配算法。其基本思路如下:

  • src的第一个字符开始和子串str的第一个字符进行比较,如果相等,则比较下一个,依次类推
  • 如果不等,则从src的第二个字符开始和子串str的第一个字符进行比较,如果相等,则比较下一个,依次类推
  • 如果不等,则从src的第三个字符开始比较.....

该算法比较简单,如果src长度为n,子串str长度为m,则时间复杂度为O(n*m):

/*
 Brute Force算法,时间复杂度为O(m*n);
 */
char *BF(const char *src, const char *str) {
    // 最终找到的位置的指针
    char *ptr = NULL;
    // src的遍历起始位置
    const char *begin = src;
    // 要查找的子串的长度
    size_t length = strlen(str);
    // 源串的长度
    size_t src_length = strlen(src);
BEGIN:
    while (1) {
        // 子串比剩余src长,则直接返回
        if (src_length - (begin - src) < length) {
            break;
        }
        // 否则从src当前位置开始依次比较
        for (int i = 0; i < length; i++) {
            // begin不等于str
            if (begin[i] != str[i]) {
                // begin后移
                begin++;
                // 重新判断并循环
                goto BEGIN;
            }
        }
        // 如果一次for循环执行完毕,表示查找到了
        ptr = (char *)begin;
        break;
    }
    return ptr;
}
int main(int argc, const char * argv[]) {
    
    __unused char *ptr = BF("hello world", "world");
    
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容