匹配算法,图像匹配算法
KMP模式匹配算法是什么？
KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。
1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。
图1改进算法的模式匹配过程示意
bm是什么意思?
bm的意思是：一种算法。
BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
BM算法主要思想描述如下
(1)模式字符串的匹配顺序是从右向左:
(a)首先将P和T对齐，即p和t对齐。
(b)然后匹配从模式字符串P的最右端字符开始，即判断p[m]和t[m]是否匹配：如果匹配成功，则向左移动判断p[m-1]和t[m-1]是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。
(2)字符串滑移启发式策略：
(a)坏字符移动启发式策略。
(b)好后缀移动启发式策略。
两种策略的使用：如果同时满足两种策略使用条件时，选两者中较大的作为模式串向右滑移的距离。
串的模式匹配算法
本文主要讲述了串的模式匹配算法，包括BF算法、RK算法、KMP算法、BM算法，使用不同的算法实现目标串查找子串，重点在于分析的过程，通过不同的算法分析提高逻辑思维能力
模式匹配的目的就是在目标串中查找与模式串相等的子串。在这里称呼主串为s，模式串为t，主串的长度为n，模式串的长度为m
暴力算法，将目标串和模式串的每个字符都进行一一比较。性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。
O(n*m)
RK算法把字符串比较问题，转换为了Hash值比较问题。
将模式串t的每个字符的比较改成了将串作为整体与目标串进行哈希值比较，这样就减少了比较次数
以前模式串与子串的比较需要比较每个字符，现在只要整体比较依次哈希值就可以。所以减少了比较次数。
哈希算法
这里我们可以发现一个Hash冲突问题，比如"abc"和"bc"的Hash值是一样的，因为最高位是0。所以还需要进行哈希冲突算法。
哈希冲突算法：
利用前一个结果计算下一个哈希值
这是因为目标串的相邻子串，其实相差的只有第一个字符和最后一个字符，其他字符是相同的，
所以我们可以利用前一个计算结果减去前一个字符串的第一个字符串，加上这个字符串的最后一个字符就够了。
针对BF的弊端，在KMP算法中可以进行多字符的跳跃对比，以此来避免目标串的不必要回溯。
例子：
简单说明一下：
真子串：
匹配：
例如：目标串："abxabcabcaby"，模式串："abcaby"
模式串的最大真子串为ab,
我们在匹配时，发现目标串的子串abcabc与模式串的前字符都匹配，最后一个字符不匹配
所以就从目标串的abcabc的后面abc开始与模式串进行匹配，而不需要匹配前面的abc了。
也就是从上一个a字符直接跳跃到了下一个a字符，而不是从b字符开始。
会存在一种情况：
实现思想：
它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的三四倍。BM算法的原理很多复杂，比较难懂，学起来比较烧脑。
实现思想和KMP算法基本上是一样的，都是先计算模式串的真子串，之后再查找真子串的大小，当出现不匹配时，直接在真子串后进行匹配，区别于KMP算法，它是从后往前匹配的
这里比上面的KMP算法增加了一个坏字符规则，可以更快的跳跃，当然KMP算法本身也可以使用坏字符规则
坏字符规则
好后缀规则
算法基础 - 朴素模式匹配算法、KMP模式匹配算法
假设我们要从 主字符串goodgoogle 中匹配 子字符串google
朴素模式匹配算法就是 通过从主字符的头部开始 一次循环匹配的字符串的挨个字符 如果不通过 则主字符串头部位置遍历位置+1 在依次遍历子字符串的字符
匹配过程
主字符串从第一位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出d 取出g 不匹配 主字符串遍历位置+1
主字符串从第二位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第三位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第四位开始 取出d 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第五位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出g 取出g 匹配
取出l 取出l 匹配
取出e 取出e 匹配 子循环结束 匹配成功
假设主字符串 长度为 n 子字符串长度为m n= m
最好的情况需要匹配m次 时间复杂度为 0(m)
例如 000000000001 匹配 00001 每次进入子循环之后 都要遍历到最后一次子循环才得出不匹配
需要匹配次数 (n-m+1) * m
最坏的情况需要匹配m次 时间复杂度为 0((n-m+1) * m)
KMP 算法的主要核心就是 子字符串在子循环内得出不匹配时 主字符串当前的判断位不需要回溯–也就是不可以变小 ，且子循环的判断位需要回溯 回溯位与子字符串本身是否具有重复结构有关 。 以此来规避无效的判断
时间复杂度为 O(n+m)
如果主串 S = "abcdefgab" 我们要匹配的子串 T = "abcdex" 如果用前面的朴素算法 ， 前5个字母完全相同
直到第6个字母 f 和 x 不同
步骤1
S: a b c d e f g a b
T: a b c d e x
接下来如果用朴素算法的话 那么应该是如下比较
步骤2
S: a b c d e f g a b
T: # a b c d e x
b 和 a 不匹配
步骤3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配
步骤4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配
步骤5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配
步骤6
S: a b c d e f g a b
T: # # # # # a b c d e x
即主串S中的第2 ，3 ， 4， 5， 6 位都与子串T的首字符不相等
对于子串T来说 如果首字符a与后面的bcdex中任意一个字符都不相等
那么对于上面的第一步来说 前五位都相等 那么 可以得到 子串首字符a 与主串的第2，3，4，5 位都不相等
即步骤2 ， 3 ，4 ，5 都是多余的 可以直接进入步骤6
如果子串的首字符串与后面的字符有相等的情况
假设S = "abcababca" T= "abcabx"
朴素算法
步骤1
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
步骤2
S: a b c a b a b c a
T: # a b c a b x
b 与 a 不匹配
步骤3
S: a b c a b a b c a
T: # # a b c a b x
c 与 a 不匹配
步骤4
S: a b c a b a b c a
T: # # # a b c a b x
a 与 a 匹配
步骤5
S: a b c a b a b c a
T: # # # # a b c a b x
b 与 b 匹配
步骤6
S: a b c a b a b c a
T: # # # # a b c a b x
a 与 c 不匹配
因为步骤1 中已经得出 前五位已经完全匹配 并且子串首字符ab 存在相同的情况 所以 步骤2，3 是多余的
直接进入步骤4 因为步骤1中已经得出 主串与子串前五位相同 同时 子串1 2 位与 子串的4 5 位相同 所以可得出
子串1 2 位 与当前主串匹配位置开始的前两位也就是主串的4 5 位匹配 所以步骤4 , 5 是多余的 可以直接进入步骤6
通过上面的两个例子我们可以发现 主串的比较位是不会回溯的 ， 而子串的比较位与子串本身结构中是否有重复相关
子串不重复 举例
S: a b c d e f g a
T: a b c d e x
子串第6位不匹配 且本身没有重复 那么下一次循环 就变成了 子串的第一位与主串的第二位比较
即子串的匹配位从6 变成了1
S: a b c d e f g a
T: # a b c d e x
子串重复 举例
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
子串在第六位发生不匹配是 前五位abcab 具有重复结构 ab 所以子串匹配位发生变化 即子串的匹配位从6 变成了 3
S: a b c a b a b c a
T: # # # a b c a b x
a 与 c 不匹配
我们可以得出 子串匹配位的值 与主串无关 只取决于当前字符串之前的串前后缀的相似度
也就是说 我们在查找字符前 ，要先对子串做一个分析 获取各个位置不匹配时 下一步子串的匹配位
前缀 ： 从头开始数 不包含最后一位
后缀 : 不是倒着数 是以和前缀相同的字符串为结尾的部分
例如 字符串 a 没有前后缀
字符串 ab 没有前后缀
字符串 aba 没有前后缀
字符串 abab 前后缀 ab
字符串 ababa 前后缀 可以是 a 可以是 aba 我们取长度最长的 即 aba
第一位时 next值固定为0
其他情况 取其公共最长前后缀的长度+1 没有则为1
因为一共子串有8位 所以在子循环内一共需要获取 8次前后缀
这里我们定义一个next数组 长度为8 里面的元素分别对应子串各个子循环内的 前后缀长度
第1位不匹配时 获取字符串为a 没有前字符串 没有前后缀 那么next[1] = 0
第2位不匹配时 获取字符串为ab 有前字符串a 没有前后缀 那么next[2] = 1
第3位不匹配时 获取字符串为aba 有前字符串ab 没有前后缀 那么next[3] = 1
第4位不匹配时 获取字符串为abab 有前字符串aba 前后缀 a 那么next[4] = 2
第5位不匹配时 获取字符串为ababa 有前字符串abab 前后缀 ab 那么next[5] = 3
第6位不匹配时 获取字符串为ababaa 有前字符串ababa 前后缀 aba 那么next[6] = 4
第7位不匹配时 获取字符串为ababaab 有前字符串ababaa 前后缀 a 那么next[7] = 2
第8位不匹配时 获取字符串为ababaabc 有前字符串ababaab 前后缀 ab 那么next[8] = 3
next数组为[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]
后来有人发现 KMP还是有缺陷的 比如 当子串 T = "aaaaax"
在5位发生不匹配 此时 next[5] = 4 接着就是 子串中的第四位a与 主串当前位置字符比较
因为子串第五位等于子串第四位相同 所以可以得出该步骤也不匹配 此时 next[4] = 3
依然不匹配 直到next[1] = 0
我们可以发现由于T串中的 2 3 4 5 位置都与首位a 相等 中间的过程都是多余的
那么可以用首位的next[1] 的值 去替代与它相等的字符后续的next[x]的值