字符串匹配算法

js 的字符串（数组元素）匹配 indexOf、includes

首先从搜索词第一个字符与字符串中的字符比较。如果匹配接着比较第二个字符。

出现不匹配的情况搜索词向后移动一位，进行比较。

。。。

如果搜索词有重复的前缀和后缀，把重复的字符串长度称为部分匹配值。

在上述匹配过程中如果匹配了部分字符串（ABCDAB）之后发现字符串不匹配，

这时可以移动的长度是：已匹配字符串总长度 - 已匹配字符串长度的部分匹配值

// 因为根据部分匹配值的前缀后缀特性，不可能在已匹配字符串长-部分匹配值这个区间中匹配成功

// 如果还能匹配的话部分匹配度就不应该是这么小。

// 在这个区间能匹配实际上就是已匹配字符串的前缀和后缀的比较！！（搜索词移动一位就错位）

。。

那么就要先求出部分匹配表。

// 注意ABABC的部分匹配值为0.前缀是A，AB，ABA，ABAB。

2.Boyer-Moore

假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。

首先，"字符串"与"搜索词"头部对齐，从尾部开始比较（能找出最远的坏字符）。

"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。

依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。

总结出"坏字符规则"：

　　后移位数 = 出现坏字符对应于搜索词的位置 - 搜索词中的最接近的位置

...

比较前面一位，"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。

此时存在"好后缀"。所以，可以采用"好后缀规则"（还是为了对齐相同字符）：

　　后移位数 = 搜索词长度 - 搜索词中的好后缀上一次出现位置

如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。

...

可以看到，"坏字符规则"只能移3位，"好后缀规则"可以移6位。所以，Boyer-Moore 算法的基本思想是，每次后移这两个规则之中的较大值。

更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。