字符串的模式匹配算法——BF算法与KMP算法

#include <iostream>
#include <string>
using namespace std;
//BF算法实现
int BF(string _str, string _patnStr)
{
  int i = 0, j = 0;
  while ((_str[i] != '\0') && (_patnStr[j] != '\0'))
  {
  if (_str[i] == _patnStr[j])
  {
    ++i;
    ++j;
  }
  else
  {
    i = i - j + 1;
    j = 0;
  }
  }
  if (_patnStr[j] == '\0')
  return i - j + 1;
  return -1;
}
//KMP算法实现
int KMP(string _str, string _patnStr)
{
  int i = 0, j = -1;
  int *next = new int[_patnStr.length()];
  next[0] = -1;
  while (i < _patnStr.length())
  {
  if (j == -1 || _patnStr[i] == _patnStr[j])
  {
    ++i;
    ++j;
    next[i] = j;
  }
  else
    j = next[j];
  }
  i = 0;
  j = 0;
  while (i < _str.length() && j < _patnStr.length())
  {
  if (j == -1 || _str[i] == _patnStr[j])
  {
    i++;
    j++;
  }
  else
    j = next[j];
  }
  if (j == _patnStr.length())
  return i - j + 1;
  else
  return -1;
}
int main()
{
  string str = "aaaaacaaaaa";
  string patnStr = "ac";
  cout << BF(str, patnStr) << endl;
  cout << KMP(str, patnStr) << endl;
  return 0;
}

5
5