目录

串的模式匹配算法：

算法目的

算法种类

BF算法（穷举法）

KMP算法

BF算法

算法的思路

具体过程

子串位置的计算

代码实现

时间复杂度

KMP算法

 求解next的方法

求next[j+1]

         使用next数组来实现过程

代码实现

next 数组的优化

代码实现

确定主串中所含子串（模式串）第一次出现的位置（定位）。

特点：速度快

Brute-Force简称为BF算法，亦称简单匹配算法，采用穷举法（将结果一一列出来的方法）的思路。

下面我们举个例子来理解一下：

主串S (正文串)：   a   a   a   a   b   c   d

子串T (模式串)：   a   b   c 

它的过程是这样的：

1.先比较前三个

发现不匹配

2.再比较后面的三个

发现还是不匹配

3.再继续比较后面的三个

发现还是不匹配

4.再继续比较

匹配成功

从S的每一个字符开始依次与T的字符进行匹配。

理解了之后，我们来看一下这个算法的具体执行过程。

我们学了串的顺序存储法之后，知道了串是用一维数组来存的，为了方便，数组下标为0的位置不存元素，从下标为1的位置开始存，所以 i 和 j 的初值都是1(i 和 j 均表示下标)。

i=1，j=1

发现相同，所以让 i++，j++，得：

i=2，j=2

 发现相同，所以让 i++，j++，得：

i=3，j=3

发现相同，所以让 i++，j++，得： 

i=4，j=4

发现不相同，所以让 i 回溯（公式：i-j+2），即 i=2，让 j 回到最开始的位置，即 j=1，得：

i=2，j=1

 重复以上的比较过程：

直到这样，发现不相同，所以再让 i 回溯（公式：i-j+2），即 i=3，让 j 回到最开始的位置，即 j=1，得：

i=3，j=1

重复以上的比较过程： 

直到这样，S 和 T 里都没有元素了，这样就匹配成功了，另外除了这种情况以外，还可能出现：

1 .S里还有元素，但是T里面已经没有元素了：

这样的话也是匹配成功了。

2 .S里面已经没有元素了，但是T里面还有元素没有匹配

这样的话是匹配不成功。

就是像上图这样算的，用当前的 i 减去子串的长度，就得到子串的位置了。

过程呢就是这样：

由于我用了string，所以下标都是从0开始的，所以：

 i 回溯时 回溯到 i-j+1的位置

 j 回退时 回退到 0 

 匹配失败时返回 -1