关于实现字符串匹配BF算法的小结

今天在学习的时候突然想起昨天的串的字符串匹配方面还有很大空缺，所以说暂时放弃刷别的转手去学习一下字符串匹配；

先介绍一下简单的字符串匹配---bf（brute force)暴力朴素匹配，可不是boyfriend哈

其实在STL中有专门对应这样功能的函数-strstr函数

strstr是C语言中的函数，作用是返回字符串中首次出现子串的地址。

但是还应该仔细研究一下算法才有意思

暴力算法的匹配情景是这样的：

设有两个串，一个为主串s，另一个为模式串或者是字串p，我们要做的是在主串中查找匹配与子串的子串，有点绕口；

如果匹配成功，确定相匹配的字串的第一个字符在主串中的位置

比如：

s="abcxyz123",p="123"

第一次匹配，p[0]！=s[0]，后面的p[1]，p[2]就不用看了

bf算法的主要步骤是酱紫的：

设两个虚拟指针i,j分别指向母串和子串的初始下标0，在i和j都比各自串的长度小的时候，就一直执行这样的循环操作：

如果s[i]==p[j]的话，俩个虚拟指针i,j分别移向下一个，

若不相等的话，j指针回溯到开始的位置0；

i指针移到上一次开头的下一个字符，重新比较；

如果j>=p.length()了，就匹配成功，返回模式中第一个字符串相等的字符在主串s的位置

不然返回0或者是-1

需要注意到的一点是：在一般情况下n>=m可能存在主串中有模式串，但n<m一定没有

这里的n指的是主串长度，m是子串长度：

 

Talk is cheap. Show me the code.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string str,sub;
 4 int bf()
 5 {
 6     int lenStr = str.length();
 7     int lenSub = sub.length();
 8     if(lenStr<lenSub)//在一般情况下n>=m可能存在主串中有模式串，但n<m一定没有
 9     return -1;
10     int i = 0,j = 0;
11     while (i < lenStr && j < lenSub)
12     {
13         if (str[i] == sub[j])
14         {
15             i++;
16             j++;
17         }
18         else
19         {
20             i = i - j + 1;
21             j = 0;
22         }
23     }
24     if (j >= lenSub)//字串遍历完
25         return i - sub.length();// 或者是return i-j
26         else
27     return -1;
28 
29 }
30 int main()
31 {
32     
33     getline(cin,str);//abababc
34     getline(cin,sub);//abc
35     int pos=bf();
36     printf("%d",pos);
37     return 0;
38 }

当然，就一些极端情况下bf算法很受被动；

比如在最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符与主串中相应的子串的比较

s="aaaaaab"

p="aab"

这样来看算法的时间复杂度就太高了，就需要一种更快更高效的算法，

那就是KMP算法