AC算法BM算法AC算法（Aho-Corasick Algorithm）AC算法是一种字符串算法，通常用于在一段文本中查询多个模式串的出现情况。
它是由Alfred V. Aho和Margaret J. Corasick于1975年提出的，并以他们的名字命名。
AC算法的原理是构建一个有限状态机（FSM），该状态机能够同时处理多个模式串的匹配。
该算法具有高效的时间和空间复杂度，并且能够在一次扫描内找到所有模式串的匹配位置。
下面将介绍AC算法的详细步骤：1. 构建Trie树（前缀树）：根据给定的模式串集合，构建一个Trie树。
Trie树是一种特殊的字典树，它能够实现快速的字符串匹配。
Trie树的根节点为一个空节点，每个节点都有多个子节点，每个子节点都代表一个字符。
从根节点到叶子节点的路径上的所有字符组成一个模式串。
2. 构建失败指针（Fail Pointer）：在Trie树中，每个节点的失败指针指向它的最长后缀节点，该后缀节点也是Trie树的节点。
如果一个节点的当前字符在其最长后缀节点的子节点中不存在，则将失败指针指向最长后缀节点的失败指针指向的节点。
如果没有最长后缀节点，则将失败指针指向根节点。
3. 在文本中匹配模式串：从文本的第一个字符开始，按照Trie树的路径进行匹配。
如果在一些节点匹配失败，则通过失败指针转移到下一个节点进行匹配，直到匹配成功或到达文本的末尾。
当匹配成功时，可以通过沿着失败指针回溯，找到其他可能的匹配位置。
4.输出匹配结果：对于每个文本字符，记录匹配的模式串。
使用一个结果链表，其中每个节点包括一个指向匹配的模式串的指针和该模式串在文本中的位置。
AC算法的时间复杂度为O(n+m)，其中n是文本的长度，m是模式串的总长度。
空间复杂度为O(m)，即模式串的长度。
BM算法（Boyer-Moore Algorithm）BM算法是一种字符串和匹配算法，通过对模式串的后缀进行预处理，实现在文本中的快速。
BF算法KMP算法BM算法BF算法（Brute-Force算法）是一种简单直接的字符串匹配算法。
它的基本思想是从主串的第一个字符开始，逐个与模式串的字符进行比较，如果匹配失败，则主串的指针向右移动一位，继续从下一个字符开始匹配。
重复这个过程，直到找到匹配的子串或者主串遍历完毕。
BF算法的时间复杂度是O(n*m)，其中n和m分别是主串和模式串的长度。
当模式串较长时，算法的效率较低。
但是BF算法的实现简单，易于理解，对于较短的模式串和主串，仍然是一种可行的匹配算法。
KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，它利用了模式串内部的信息，避免了不必要的比较。
KMP算法引入了一个next数组，用于记录模式串中每个位置对应的最长可匹配前缀子串的长度。
KMP算法的基本思想是，当匹配失败时，不是简单地将主串指针右移一位，而是利用next数组将模式串的指针向右移动若干位，使得主串和模式串中已经匹配的部分保持一致，减少比较次数。
通过预处理模式串，计算出next数组，可以在O(n+m)的时间复杂度内完成匹配。
BM算法（Boyer-Moore算法）是一种高效的字符串匹配算法，它结合了坏字符规则和好后缀规则。
BM算法从模式串的末尾开始匹配，根据坏字符规则，如果在匹配过程中发现了不匹配的字符，可以直接将模式串向右滑动到该字符在模式串中最右出现的位置。
BM算法还利用了好后缀规则，当发现坏字符后，可以根据好后缀的位置和模式串的后缀子串进行匹配，从而减少不必要的比较。
通过预处理模式串，计算出坏字符规则和好后缀规则对应的滑动距离，可以在最坏情况下实现O(n/m)的时间复杂度。
总结来说，BF算法是一种简单直接的字符串匹配算法，适用于较短的模式串和主串；KMP算法通过预处理模式串，利用next数组减少比较次数，提高了匹配效率；BM算法结合了坏字符规则和好后缀规则，利用了更多的信息，是一种高效的字符串匹配算法。
BM算法详解BM算法 后缀匹配，是指模式串的⽐较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮⼒匹配算法的改进。
为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。
利⽤好后缀和坏字符可以⼤⼤加快模式串的移动距离，不是简单的++j，⽽是j+=max (shift(好后缀), shift(坏字符)) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个字符，继续⽐较，如下图：坏字符出现在模式串中，这时可以把模式串第⼀个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图： 此处配的图是不准确的，因为显然加粗的那个b并不是”最靠右的”b。
⽽且也与下⾯给出的代码冲突！我看了论⽂，论⽂的意思是最右边的。
当然了，尽管⼀时⼤意图配错了，论述还是没有问题的，我们可以把图改正⼀下，把圈圈中的b改为字母f就好了。
接下来的图就不再更改了，⼤家⼼⾥有数就好。
为了⽤代码来描述上述的两种情况，设计⼀个数组bmBc['k']，表⽰坏字符‘k’在模式串中出现的位置距离模式串末尾的最⼤长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。
如下图： 数组bmBc的创建⾮常简单，直接贴出代码如下：1 void preBmBc(char *x, int m, int bmBc[]) {23 int i;45 for (i = 0; i < ASIZE; ++i)67 bmBc[i] = m;89 for (i = 0; i <= m - 1; ++i)1011 bmBc[x[i]] = m - i - 1;1213 } 代码分析：ASIZE是指字符种类个数，为了⽅便起见，就直接把ASCII表中的256个字符全表⽰了，哈哈，这样就不会漏掉哪个字符了。
BM立体匹配算法的参数详解1. 最小视差（Minimum Disparity）：表示在计算深度图时允许的最小视差值，即物体最近处的深度差异。
选择合适的最小视差值对于过滤无意义的区域非常重要。
2. 最大视差（Maximum Disparity）：表示在计算深度图时允许的最大视差值，即物体最远处的深度差异。
选择合适的最大视差值可以防止视差计算的误差。
3. 视差窗口大小（Disparity Window Size）：表示计算每个像素的视差时，使用的窗口大小。
较大的窗口尺寸可以提供更准确的深度信息，但也会增加计算时间。
通常情况下，窗口大小是一个奇数，最常见的是3、5或74. 匹配代价度量（Matching Cost Metric）：用于计算两个像素之间的匹配代价的度量方法。
最常见的度量方法是灰度差异和绝对差异，也可以根据特定的应用选择适当的度量方法。
5. 匹配代价聚合（Matching Cost Aggregation）：用于减少匹配代价图像中的噪声和不一致性的技术。
常用的方法包括平均代价和双边滤波。
6. 视差图优化（Disparity Map Optimization）：通过优化视差图像，减少错误匹配和噪声，并提高深度估计的准确性。
常用的方法包括视差图扩张、视差图填充和视差图平滑。
7. 左右一致性检查（Left-Right Consistency Check）：用于消除左右图像之间不一致匹配的误差。
该步骤通过检查左右视图之间的匹配来得到更准确的视差图。
8. 剔除无效区域（Invalid Region Exclusion）：根据特定应用需求，去除由于遮挡、反射等原因导致的无效区域。
可以使用其他传感器信息或额外的图像处理技术来实现。
9. 空洞填充（Occlusion Filling）：通过使用图像分割或插值算法填充由遮挡产生的空洞。
这可以提供更完整和连贯的深度图像。
10. 算法效率（Algorithm Efficiency）：BM算法的计算效率对于实时应用很重要。
