暴力算法

以主串中每一个字符作为开头，与模式串进行比较。复杂度。

特点是比较的时候主串和模式串的指针都前移，失败后主串和模式串的指针都后移。

KMP算法

当B和C匹配失败的时候，之前的匹配一定是成功的，也就是说主串失败点B之前一定是ABCA，那么下一次匹配的时候可以直接将模式串A与主串中第二个A对齐，然后从主串失败点B继续匹配。

根据这个原理可以预先计算一个next表：

失败时模式串的字符	A	B	C	A	C
-	1	1	1	2

当失败在模式串C处，查表得next值为2，也就是从模式串的第二个位置继续匹配。

实际匹配过程中动的只有指针，主串指针从左向右依次移动，没有后退没有跳跃。模式串指针则根据next表进行跳跃。复杂度为。

先比较主串最后一个字符B与模式串最后一个字符F，匹配失败，我们知道如果要匹配成功，主串中B也一定与模式串中b匹配，而模式串后面一大段都没有“B”,所以可以快速将模式串移动到两个B对齐的位置。
根据这个原理可以预先计算一个bc表：

失败时主串的字符	A	B	C	D	E	F	H	I	J	K	L
1	2	3	4	5	6	0	0	0	0	0

我们同样可以预先计算一张bc表，当匹配失败时可以查表快速移动。这种策略通常从后向前比较，因为大多数的字符串匹配不成功的概率比匹配成功的概率大，所以从后向前比较效率更高。

BM算法同样兼顾KMP算法的思想，不过BM算法是从后向前匹配，所以需要生成一个倒着的next表，称之为gs表。

BM算法每当匹配失败时，分别查bc表和gs表，取这两个表中移动最快的值。

匹配过程中主串指针有跳跃的情况，这就说明它的效率可以超过线性。最好的情况复杂度为,最坏情况为。