字符串匹配算法之BF(Brute-Force)算法

简介:

  蛮力搜索,比较简单的一种字符串匹配算法,在处理简单的数据时候就可以用这种算法,完全匹配,就是速度慢啊。

基本思想

  从目标串s 的第一个字符起和模式串t的第一个字符进行比较,若相等,则继续逐个比较后续字符,否则从串s的第二个字符起再重新和串t进行比较。

   依此类推,直至串t 中的每个字符依次和串s的一个连续的字符序列相等,则称模式匹配成功,此时串t的第一个字符在串s 中的位置就是t 在s中的位置,否则模式匹配不成功。

具体实现

复制代码
  int BFindex(String S, String T)  
{  
    if (S.size() < 1 ||  T.size() < 1 ) 
        return -1;
 
    int i = 0, j = 0;
    while (i < S.size() && j < T.size())  
    {  
        if (S[i] == T[j])  
        {  
            ++i; ++j;  
        }
        else 
        {  
            i = i- j+ 2;  
            j = 1;  
        }  
    }  
    if(j > T[0]) return i - T[0];  
    return ERROR;  
}         
复制代码

 

知识共享许可协议
本文 由 cococo点点 创作,采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载,请注明出处:
转载自:cococo点点 http://www.cnblogs.com/coder2012

相关文章
|
8月前
|
机器学习/深度学习 算法
CF1029A Many Equal Substrings(kmp!!!!最通俗易懂的文章模板)
CF1029A Many Equal Substrings(kmp!!!!最通俗易懂的文章模板)
34 0
|
算法
字符串匹配算法(BF&&KMP)
字符串匹配算法(BF&&KMP)
94 0
|
算法 C语言
C 语言| 字符串匹配BF算法与RK算法
字符串匹配算法最经典的手段是BF算法,字符串匹配即给出一个主串S,根据模式串T中的字符串,找出在主串中第一次出现的位置,这个就是字符串匹配,简而言之即给一个规定的内容T,在大范围S中找到一个与之对应的,且第一次出现的位置。
|
算法 语音技术 Python
Python算法:Brute-Force算法查找字符串子串位置
Python算法:Brute-Force算法查找字符串子串位置
92 0
Python算法:Brute-Force算法查找字符串子串位置
|
存储 算法
【字符串匹配算法:BF & KMP】
【字符串匹配算法:BF & KMP】
【字符串匹配算法:BF & KMP】
|
算法
Brute-Force模式匹配算法
Brute-Force匹配算法,翻译过来可以叫暴力匹配算法,典型应用场景就是字符串的匹配问题,比如寻找一个子串在主串中第一次出现的下标。这种匹配算法的逻辑是这样的:选取主串中指定位置作为匹配的起点(这篇文章使用的是首位作为起点),将子串起点与该起点对比,比对成功后起点后移一位,子串的起点同样后移一位继续比较,直到将子串与主串中全部匹配;若是中途出现比对失败的情况,则将主串从原起点的下一位开始继续这种比较。下面就根据BF算法使用while循环和for循环来分别实现字符串的匹配问题。
182 0
Brute-Force模式匹配算法
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
|
人工智能 BI
CF1398C. Good Subarrays(思维 前缀和)
CF1398C. Good Subarrays(思维 前缀和)
75 0
CF1567D. Expression Evaluation Error(思维 贪心)
CF1567D. Expression Evaluation Error(思维 贪心)
48 0