字符串匹配算法

1、BF算法

假设现有一字符串，“BBC ABCDAB ABCDABCDABDE”将其称为给定串，相应有一匹配串“ABCDABD”。

两个串的第一个字母先相互比较:

可得第一个字符不相同，则继续向后比较，直到比较到第一个字符相同，如下图：

然后继续比较，直到发现给定串中的字符与匹配串中的不同，这时BF算法的思想是将匹配串与给定串的当前位置的下一位进行比较，这会导致很多重复比较，时间复杂度到达O（n*m）,n代表给定串的长度，m代表匹配串的长度。

2、KMP算法

此种算法，后面需要用到部分匹配表，所以先讲一下部分匹配表。我们都知道前缀就是一个字符串中除了最后一个字符之外的所有字符组合，后缀是一个字符串中除了第一个字符之外的所有字符的组合。

以匹配串“ABCDABD”为例，"A"的前缀和后缀都为空集，共有元素的长度为0；　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；"ABCDAB"的前缀为[A, AB, ABC, ABCD,ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。因此，可以得到匹配串的部分匹配表:

此种算法前半部分和BF算法一样，都是从第一个字符开始比较，然直到找到与匹配串第一个字符相匹配的位置，然后再继续比较，直到与给定串不匹配，此时，KMP的做法是通过部分匹配表来进行移位，有公式：移动位数 = 已匹配的字符数 - 对应的部分匹配值（已匹配字符的最后一个字符）。

以到达此步为例：已匹配的字符数为6，B的部分匹配值为2，所以移动6-2=4位，到如下:

此时移动2-0=2位，到如下:

此时移动1位，到如下:

此时移动6-2=4位，到如下：

达到完美匹配，此时如果还想找出字符串的全部匹配串，则移动7-0=7位。

时间复杂度是O（n+m）。

3、Boyer-Moore算法

（暂且不管坏字符和好后缀的定义，后文介绍）

坏字符规则：移动为数 = 坏字符的位置 - 匹配串中上一次出现的位置（若坏字符不出现在匹配串中，则上一次出现位置为-1）

好后缀规则：移动为数 = 好后缀的位置（以好后缀最后一个位置为准） - 匹配串中上一次出现的位置（若好后缀在匹配串中不重复出现，则上一次出现位置为-1）

假设现有一字符串，“HERE IS A SIMPLE EXAMPLE”将其称为给定串，相应有一匹配串“EXAMPLE”。

先从尾部开始比较，可以看到S与E不匹配，则将S称为坏字符，此时用坏字符规则，则移动为数为6-（-1）=7位，得到如下：

此时用坏字符规则，则移动为数为6 - 4=2位，得到如下：

此时的MPLE,PLE,LE,E都称为好后缀，此时用好后缀规则，则移动为数为6 - 0 = 6位，得到：

此时用坏字符规则，则移动为数为6 - 4 = 2位，得到：

此时达到完美匹配，如果还想找出字符串的全部匹配串，则移动6-0=6位。

end。