字符串匹配算法--Brute-Force算法

Brute-Force(暴力)算法是字符串匹配中最简单也是最容易理解的算法。

主要思想是按顺序遍历母串，将每个字符作为匹配的起始字符，判断是否匹配字串。若第一个字符与字串匹配，则比较下一个字符，否则回退到母串与字串比较的第一个字符的下个字符，继续比较。

Brute-Force算法的时间复杂度为O(mn).

步骤如图例所示：

(图来自《数据结构》严蔚敏，吴伟民 P80)

我实现的一个例子：

#include <iostream>

#include <string>

using namespace std;

int main()

{

  string str("ababcabcacbab");

  string pattern("abcac");

  size_t i=,j=,index=-;

  while(i<str.size() && j<pattern.size())

    {

      if(str[i] == pattern[j])

        {

          ++i;

          ++j;

        }

      else

        {

          i = i - j + ;

          j=;

        }

      if(j == pattern.size())

        index = j;

      else

        index = -;

    }

  cout << "str: " << str << endl;

  cout << "pattern: " << pattern << endl;

  cout << "index: " << index << endl;

}

运行结果：

巴特西

字符串匹配算法--Brute-Force算法

最新文章

热门文章