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

引言

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

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

概述

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

我们通过比较文本串的和匹配串的第一个字符来开始

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

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

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

如果文本串的一个字符和匹配串的第一个字符相匹配，我们向前移动到匹配串第二个字符和文本串的下一个字符做匹配

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

匹配串相匹配

代码

/*--------------------------------
*   日期：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

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>