[算法系列之十二]字符串匹配之蛮力匹配

简介:

引言

字符串匹配是数据库开发和文字处理软件的关键。幸运的是所有现代编程语言和字符串库函数,帮助我们的日常工作。不过理解他们的原理还是比较重要的。

字符串算法主要可以分为几类。字符串匹配就是其中之一。当我们提到字符串匹配算法,最基本的方法就是所谓的蛮力解法,这意味着我们需要检查每一个文本串中的字符是否和匹配串相匹配。一般来说我们有文本串和一个匹配串(通常匹配串短于文本串)。我们需要做的就是回答这个匹配串是否出现在文本串中。

概述

字符串蛮力匹配法的原理非常简单。我们必须检查匹配串的第一个字符与文本串的第一个字符是否相匹配,就如下图片所述。

这里写图片描述
我们通过比较文本串的和匹配串的第一个字符来开始

如果他们不匹配我们移向文本串的第二个字符。现在我们比较匹配串的第一个字符和文本串第二个字符。如果他们不匹配我们继续向前移动,直到我们遇到一个相匹配的或直到我们到达文本串的最后。

这里写图片描述
因为文本串第一个字符和匹配串的第一个字符不匹配,我们向前移动到文本串的的第二个字符。现在我们比较文本串的第二个字符和匹配串的第一个字符!

假设第一个字符匹配,我们移向匹配串的第二个字符去和文本串的下一个字符比较。如下面图片所示。

这里写图片描述
如果文本串的一个字符和匹配串的第一个字符相匹配,我们向前移动到匹配串第二个字符和文本串的下一个字符做匹配

如果仅仅是因为匹配串的第一个字符与文本串的某个字符相匹配,那并不意味着这个匹配串出现在文本串中,也仅仅是第一个字符出现在文本串中,其他说明不了。我们必须向前移动匹配串,看看完整的匹配串是否包含在文本文本串中。

这里写图片描述
匹配串相匹配

代码

/*--------------------------------
*   日期:2015-02-05
*   作者:SJF0115
*   题目: 字符串匹配之蛮力匹配
*   博客:
------------------------------------*/
#include <iostream>
using namespace std;


int SubString(string text,string pattern){
    int m = text.size();
    int n = pattern.size();
    // 蛮力匹配
    for(int i = 0;i < m - n;++i){
        int j = 0;
        while(j < n && text[i+j] == pattern[j]){
            ++j;
        }//while
        // match
        if(j == n){
            return i;
        }//if
    }//for
    return -1;
}

int main(){
    string text("hello world!");
    string pattern("o wo");
    int result = SubString(text,pattern);
    cout<<"下标位置->"<<result<<endl;
    return 0;
}

复杂度

就像我说的这个算法是缓慢的。实际上每一个算法,只要在它的名字中包含“蛮力”二字,这个算法都是很缓慢的,其时间复杂度是O(n*m)。这里m是文本串的长度,而n是匹配串的长度。

原文连接

Computer Algorithms: Brute Force String Matching

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