字符串匹配算法（上）

1、BF（暴力匹配）算法的定义

BF算法，即暴力（Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将主字符串S的第一个字符与子串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符；若不相等，则比较S的第二个字符与T的第一个字符，依次比较下去，直到得出最后匹配结果。

2、BF的解题思路

BF算法的定义比较难懂，下面来举个例子：

假设我们给出”abaeaabcda"作为主串，“abcd"作为子串，我们的目标是查找字串是否在主串中出现，若出现，则返回主串的第一个匹配的下标;若未出现，则返回-1.

最开始i,j都分别对应主串和子串的0下标，如果i和j下标对应的字符相同，则i++,j++

当i和j下标对应字符不同时，i回到之前匹配失败的起始位置加1，即j=j-i+1;j回到最开始，即j=0;

此时i和j下标对应字符不等，i=i-j+1,即i=2;j=0;

此时i与j下标对应字符相同，i++,j++

此时i与j下标对应字符不同，i=i-j+1,即i=3;j=0 以此类推，直到i=5,j=0时，i++,j++…

直到 i=9,j=4

子串遍历完成，说明在主串中找到字串，子串在主串第一个字符下标为i-j=5;

若主串先遍历完成，则说明主串没有这个子串。

3、代码实现

// 字符串匹配法 BF

//str:主串

//sub:子串

//返回值：返回子串在主串的下标。如果没有返回-1；

#include <stdio.h>
#include <string.h>**
int BF(char* str, char* sub)
{
  if (str == NULL || sub == NULL)//如果子串或者主串为空，则输出-1
  {
    return -1;
  }
  int lenstr = strlen(str);
  int lensub = strlen(sub);
  int i = 0;
  int j = 0;
  while (i < lenstr && j < lensub)//主串和子串都没有遍历结束
  {
    if (str[i] == sub[j])
    {
      i++;
      j++;
    }
    else
    {
      i = i - j + 1;
      j = 0;
    }
  }
  if (j >= lensub)//子串遍历完成，返回主串字符对应下标值
  {
    return i-j;
  }
  else//若子串未遍历完成，则是主串遍历完成，表示在主串中未找到子串
  {
    return -1;
  }
}
int main()
{
  printf("%d\n", BF("abaeaabcda","abcd"));
  printf("%d\n", BF("aeceaabada", "abcd"));
  return 0;
}

输出结果为：