一、数据结构“串”的模式匹配算法中的BF算法里的i-j2
i-j+2就是匹配不成功然后指针回到起始位置再加1。
i-j+2 == i-(j-1)+1;
j-1是j移动的距离（j看作从1开始，而不是从0开始）；i-（j-1）是i回到与子串比较的起始位置（不是一直回到i=1，i在多次匹配中不断的变大）。
然后[i-(j-1)] +1 就是回到起始位置之后再往后进一位。
例如名列前茅次匹配的时候，开始时i=1，j=1； 然后匹配失败，回溯后i+1，第二次匹配开始时就是i=2，j=1。再匹配失败，回溯到起始位置i=2后 i+1，第三次匹配开始时就是i=3，j=1；以此类推。
i=i-j+2 是数组下标从1开始的情况；
i=i-j+1 是数组下标从0开始的情况。
BF算法
BF算法介绍
Brute-Force简称为BF算法，亦称为简单匹配算法，采用穷举的思想。
S：a a a a b c d 主串：正文串
T： a b c 子串：模式串
算法的思路是从S的每一个字符开始依次与T的字符进行匹配。
BF算法设计思想
Index_BF(S, T)
将主串的第pos个字符和模式串的名列前茅个字符比较,
若相等，继续逐个比较后续字符;
若不等，从主串的下一字符起，重新与模式串的名列前茅个字符比较。
直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列名列前茅个字符的序号即匹配成功。
否则，匹配失败，返回值-1。
延伸阅读：
二、KMP算法
KMP算法是一种字符串匹配算法，是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。其核心是利用字符串匹配失败后的的信息从而减少字符串与模式串的匹配次数从而提高字符串匹配的效率。
假设主串为s=”ababcabdabcabca”、模式串为p=”abcabc”，指针i、j分别指示主串和模式串所比较字符的位序号。
在名列前茅趟匹配中，由于,,,因此i=2,j=2;
按照之前的思路，我们应当修改i为1，j为0后再次进行比较。但由于,,因而,所以此时不必从i为1处进行匹配，而只需匹配和;
在第三趟匹配中，由于,显然此时有，。因为,,所以无需与和进行比较，而只需匹配和；又因为,所以,这两次比较也可以通过前次匹配的信息来略过；
通过以上的分析，我们不难发现，我们可以利用模式串自身的信息来计算模式串匹配失败后下一次所要匹配的位置，而主串的比较位置不需要回退。
当某次匹配失败时，有那么 = 。如果在模式串中存在这样的k，使得 = ,那么在下一次匹配时，我们便只需匹配和。特别地，当k=0时，我们应当匹配和。(k应当使得…最长)
通过以上的分析，我们可以知道其实该算法的关键在于获取一个next数组，通过该数组来记录模式串中各个位置的最长前缀子串从而避免重复匹配的出现。也就是说模式串每次开始匹配的位置由模式串本身来决定。
京公网安备 11010802030320号