山东白癜风医院 http://baidianfeng.39.net/a_zhiliao/131226/4317323.htmlBF算法（BruteForce）:暴力匹配算法，如果在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串，主串记长度作n，模式串长度记作m，nm，在主串中检查位置分别是0,1,2,3,4...n-m，一共匹配n-m+1次，也就是一共匹配n-m+1个子串。
暴力匹配过程图解：
第一步：主串和模式串匹配位置初始化
第二步：挨个匹配，判断i和j指向的字符是否相等
第三步：如果i和j指向的字符不匹配，i向后移动一位，j重新设为0
程序实现：
intBF(strings1,strings2){//第一步：i和j进行初始化操作inti=0;//主串位置intj=0;//模式串位置//第二步：挨个匹配while(is1.length()js2.length()){//第三步：如果i和j指向d嗯字符相等，那么i和j都向后移动一位，如果i和j指向的字符不相等，i减去j，然后再加1，j重新从0开始if(s1==s2[j]){i++;j++;}else{i=i-j+1//i-j：表示重新回到开始位置，然后加1，表示遇到坏字符向后挪一个位置继续匹配j=0;}}if(j==s2.length()){//j从零开始，如果等于模式串长度，说明匹配完成returni-j;}else{return-1;}}
每次遇到不匹配字符，i指针就要回溯回去，效率明显很低。是否可以利用已经匹配的部分，保持i指针不回溯，通过修改j指针，让模式串移动到一个有效位置？当某一个字符与主串不匹配时，j指针应该移动到哪？
例如，当字符C和D不匹配时：
因为在前面有相同的A匹配，所以j移动到1的位置
再举例，如图：
j移动到2的位置，因为前面已经有两个字符匹配
每一个位置都有可能发生不匹配，也就是每一个j位置都对应一个下次j指向位置k，在这里使用next数组保存，next[j]=k，表示当主串！=模式串[j]时，j指针应该指向的下一个位置值。
当j=0时，不匹配：
j已经在最左边了，不可能再移动了，此刻应该让i指针左移，j相当于减少一个位置，j从0回溯到-1，所以next[0]=-1，一种理解方式，主要为了防止出现死循环k=next[k]，当出现next[0]=-1,说明要回溯到开始位置重新匹配，后面会涉及到。(模式串向右移动，j向左移动)
当j=1时，不匹配：
j指针一定是左移到0位置，前面只有这一个位置
当j=3时，不匹配：
j指针一定是左移到1位置，前面有1个A字符匹配
当j=5时，不匹配：
j指针一定是左移到2位置，前面有2字符AB匹配
规律图解：
总结：当模式串第j个字符和主串第i个字符匹配失败，j要移动到下一个位置k，k前面的字符与k之后到j之间的字符是最长公共前后缀，P是模式串，公式P[0~k-1]==P[j-k~j-1]。
证明：j为什么可以直接移动到k的位置？
当T！=P[j]时：
第一步：当T和P有公共前后缀时，T!=P[j]，[T[i-j~i-1]==P[0~j-1]
第二步：当T和P有公共前后缀时，模式串P满足P[0~k-1]==P[j-k~j-1]
第三步：当j==k时，根据①②仍然满足T[i-k~i-1]==P[0~k-1]
总结：当T!=P[j]时，如果最长公共前后缀的长度为k，则下次匹配指针j可以移动到第k位，next[j]=k，这里是以下标为0作为基准。
第一种情况，next[j]数组求解：
P[j]=P[k]时，next[j]=k，则next[j+1]=k+1=next[j]+1;
第二种情况，next[j]数组求解：
P[j]!=P[k]，指针k应该回溯到next[k]位置，k=next[k]
next数组实现分析：
因为需要找出最长公共前后缀，所以开始比较肯定需要错位比较，j指针控制上面的模式串p，k指针控制下面的模式串p。
换种思路理解，为什么可以把主串和模式串的比较转换成模式串和模式串的错位比较？
在匹配过程中，我们始终都是在找相同，遇到不匹配，最长公共前后缀到达极限，上面已经证明了最长公共前后缀的有效性，可以提高效率，就有匹配问题，转换成了对模式串下手，求模式串的最长匹配前后缀问题。
voidgetNext(strings1,intnext[]){intj=0;//负责上面模式串intk=-1;//负责下面模式串next[0]=-1;//j==0,k=-1,next[j]=k,意味着重新开始匹配while(js1.length()-1){if(k==-1
s1[j]==s1[k]){//如果k==-1，也就是意味着下面模式串要重新开始匹配主串（其实还是匹配自己）//算的是下一项前面的最大公共前后缀next[j+1]=k+1;//如果p[j]==p[k]，next[j+1]=next[j]+1，满足上面的第一种情况推导k++;j++;}else{//如果p[j]!=p[k],k应该指向下一个位置，也就是回溯，下一个位置值又提前存储在当前k指向next[k]，所以只需要把k赋值为next[k]，下一次继续拿着当前k指向的next[k]，去向前移动让k指向新的值,k=next[next[k]]。k=next[k];//终归来说都是在假设已经存在最长公共前后缀时，当前k和j指向的值不匹配，规律推导。}}}
next数组优化：
假设P为模式串，T为主串，当T！=P[j]，会存在模式串指针j不能一次性回溯到位的情况，如下图：
按照next数组求解方法，j应该回溯到下标1的位置，但是回溯之后，仍然出现T!=P[j]，因为P[j]==P[next[j]]，所以应该让j直接回溯到0位置，也就是继续回溯到next[1]=0。
优化后程序：
voidgetNext(strings1,intnext[]){intj=0;//负责上面模式串intk=-1;//负责下面模式串next[0]=-1;//j==0,k=-1,next[j]=k,意味着重新开始匹配while(js1.length()-1){if(k==-1
s1[j]==s1[k]){//如果k==-1，也就是意味着下面模式串要重新开始匹配主串（其实还是匹配自己）k++;j++;if(s1[j]==s1[k]){next[j]=next[k];//k的next[k]表示多向前推进一步}else{next[j]=k;}}else{//如果p[j]!=p[k],k应该指向下一个位置，也就是回溯，下一个位置值又提前存储在当前k指向next[k]，所以只需要把k赋值为next[k]，下一次继续拿着当前k指向的next[k]，去向前移动让k指向新的值,k=next[next[k]]。k=next[k];//终归来说都是在假设已经存在最长公共前后缀时，当前k和j指向的值不匹配，规律推导。}}}
KMP算法程序：
intKMP(strings1,strings2){inti=0;//主串的开始下标intj=0;//模式串的开始下标while(is1.length()js2.length()){if(j==-1
s1==s2[j]){//当j为-1时，要移动的是i,j也要归0i++;j++;}else{//i=i-j+1;与暴力匹配最大的不同，去就是i不需要回溯了j=next[j]//j回到指定位置}}if(j==s2.length()){returni-j;}else{return-1;}}
RK算法（Rabin-Karp）:根据Rabin和Karp两位发明者的名字命名，具体思路通过哈希算法对主串的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值进行比较大小，如果某个子串的哈希值与模式串相等，说明匹配成功。
如何高效计算哈希值？
例如，10进制数字类型字符串就可以转换成10进制数值，对于26个字母类型字符串，每个字母对应26进制的一个数值，最终也可以转换为10进制数值。
如果子串比较长，那么算出来的值就相对比较大，有可能发生数据溢出，怎么办呢？
此时可以允许哈希值重复，比如可以让子串每个字符对应的26进制值相加，遇到匹配项就停下来，这种时候可能存在哈希值一样，但是实际字符串并不匹配的情况存在，所以需要比较一下字符串，查看是否可以完全匹配，这种效率相对来说还是比暴力匹配高很多。
BM（Boyer-Moore）算法：例如，在文本编辑器word中查一个单词，性能比KMP高出3到4倍。
BK和RK算法的匹配规则，如果遇到不匹配的字符，都是选择让模式串往后一次滑动一位：
主串中存在c，在模式串中是不存在的，模式串向后滑动的时候，只要与c存在重合，肯定无法匹配，可以选择把模式串移动到c的后面：
BM算法包含两部分，坏字符规则和好后缀规则：
第一种--坏字符规则：
BF和RK匹配规则，下标从左到右：
BM坏字符规则，下标从右到左：
从模式串的尾巴往前倒着匹配，当发现某个字符无法匹配的时，就把这个没有匹配的字符叫作坏字符（主串中的字符）。
坏字符c在模式串中查找，发现模式串中并不存在这个字符，向后移动3位，重新从后面向前查找。
重新匹配发现，a和d仍然不能匹配成功，但是坏字符a在模式串中可以找的到，那么再向后移动时仍然移动3位么？这种情况下只需要移动两位，让坏字符a和模式串中的a对齐，再重新从后向前匹配。
规律总结：当发生不匹配的时候，可以把坏字符对应的模式串中的字符下标赋值给si，如果坏字符在模式串中存在，可以把这个坏字符在模式串中的下标赋值给xi，如果不存在把xi赋值-1，模式串向后移动的位数为si-xi。
如果坏字符在模式串中多处出现，在计算xi的时候，选择最靠后那个，防止滑动过多，忽略本应该可以匹配的情况。
如果si-xi结果为负数怎么办？
例如，主串aaaaaaaaaaaaa，模式串baaa,此刻si为0，a为3，不会向后移动，反而变成向前移动。
引入第二种--好后缀规则：当模式串滑动到图中的位置的时，模式串和主串有2个字符是匹配的，倒数第3个字符发生了不匹配。
此时可以把已经匹配的bc叫作好后缀，记作{u}，拿着好后缀在模式串中查找，如果找到了另一个跟好后缀相匹配的子串{u*}，就将模式串滑动到子串{u*}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于好后缀子串{u}，直接将模式串滑动到主串中{u}的后面，因为前面的任何一次往后滑动，都不会匹配主串中的{u}。
如果直接滑动到主串中{u}好后缀的后面，有可能错过最佳匹配：
当模式串滑动到本身前缀与主串中{u}的后缀有部分重合的时候，重合部分而且相等，就有可能存在完全匹配的情况。
在这里不仅要看好后缀在模式串中是否有另一个匹配的子串，还要考察好后缀的后缀子串是否存在跟模式串的前缀子串匹配。
当模式串和主串中的某个字符不匹配时，选择用好后缀规则还是坏字符规则？
计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的作为模式串往后滑动的位数，避免出现根据坏字符规则得到往后滑动的位数存在负数。
一只小跃跃
