字符串匹配算法之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点点博客园博客,原文链接:http://www.cnblogs.com/coder2012/p/3279916.html,如需转载请自行联系原作者

相关文章
|
13天前
|
算法
【优选算法】—— 字符串匹配算法
【优选算法】—— 字符串匹配算法
|
13天前
|
人工智能 算法 测试技术
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
|
2天前
|
算法
KPM算法求字符串的最小周期证明
公式 `ans = n - LPS[n-1]` 描述了最小周期,其中 `n` 是子串长度,`LPS[n-1]` 是前缀函数值。证明分为特殊情况和一般情况:对于完整周期字符串,`LPS[n-1] = 3*T`,故 `ans = T`;对于非完整周期,通过分析不同长度的 `[末部分]` 和 `[前部分]`,展示 `ans` 始终等于周期 `T` 或由 `[e][b]` 构成的最小周期,从而证明公式正确。
|
13天前
|
算法 搜索推荐 程序员
第六十五练 字符串匹配 - Rabin-Karp算法
第六十五练 字符串匹配 - Rabin-Karp算法
18 1
|
13天前
|
算法 搜索推荐 程序员
第六十四练 字符串匹配 - Boyer-Moore算法
第六十四练 字符串匹配 - Boyer-Moore算法
20 0
|
13天前
|
算法 搜索推荐 程序员
第六十三练 字符串匹配 - KMP算法
第六十三练 字符串匹配 - KMP算法
18 2
|
13天前
|
算法 C语言 人工智能
|
13天前
|
算法
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
29 1
|
13天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
13天前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
30 0