vlambda博客
学习文章列表

【数据结构与算法】动画:什么是 BF 算法 ?

码农有道

 




本文是图解 什么是 BF算法、KMP算法、BM算法 三部曲之一。

定义

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

它的核心思想与操作是:

  • 对于给定的主串 S 与子串 P ,主串 S 的长度为 N,子串 T 的长度为 M ;

  • 首先,将 S[1] 和 T[1] 进行比较;

  • 若相等,则再比较 S[2] 和 T[2] ,一直到 T[M] 为止;

  • 若 S[1] 和 T[1] 不等,则 T 向右移动一个字符的位置,再依次进行比较;

动画演示

【数据结构与算法】动画:什么是 BF 算法 ?

图片演示

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

【数据结构与算法】动画:什么是 BF 算法 ?

代码描述

int index( String S, String T, int pos ){
    int i = pos;                        // i 表示主串 S 中当前位置下标
    int j = 1;                            // j 表示子串 T 中当前位置下标

    while( i <= S[0] && j <= T[0] ){    // i 或 j 其中一个到达尾部则终止搜索
        if( S[i] == T[i] ){             // 若相等则继续进行下一个元素匹配
            i++;
            j++;
        }else {                         // 若匹配失败则 j 回溯到第一个元素重新匹配
            i = i - j + 2;              // 将 i 重新回溯到上次匹配首位的下一个元素
            j = 1;
        }
    }

    if( j > T[0] ){
        return i - T[0];
    }else {
        return 0;
    }
}

总结

BF算法 在主串和字串匹配失败时,主串进行的回溯操作会影响效率,回溯之后,主串与字串有些部分比较是没有必要的。这种简单的丢弃前面的匹配信息是 BF算法 之所以效率低效的一个重要因素。

KMP算法BM算法 将在后续分别进行详细介绍,敬请关注。

推荐阅读:




专注服务器后台技术栈知识总结分享

欢迎关注交流共同进步

码农有道 coding


码农有道,为您提供通俗易懂的技术文章,让技术变的更简单!