数据结构与算法<四>

其他更多java基础文章：
java基础学习(目录)

这系列是根据极客时间《数据结构与算法之美》这个课程做的笔记

本篇目录

广度和深度优先算法

BF及RK算法

BM算法

KMP算法

Sunday算法

Trie树

AC自动机

广度和深度优先算法

广度优先搜索（BFS）

广度优先搜索（Breadth-First-Search）简称BFS，其实是一种“地毯式”层层推进的搜索策略，（先查找离起始顶点最近的，然后是次近的，依次往外搜索）

有三个重要辅助变量visited，queue，prev

visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点q被访问，那相应的visited[q]会被设被设置为true。
queue是一个队列，用来存储已经被访问，但相连的顶点还没被访问的顶点。因为广度优先搜索是逐层访问的，只有把第k层的顶点都访问完成之后，才能访问第k+1层的顶点。当我们访问到第k层的时，要把第k层的顶点记录下来，稍后才能通过第k层来找第k+1层的顶点。
prev用来记录搜索路径。当我们从顶点s开始，广度优先搜索到顶点t后，prev数组中存储的就是搜索的路径。不过这个路径是反向存储的，prev[w]存储的是，顶点w是从哪个前驱顶点遍历过来的。

BFS的时间复杂度

时间复杂度：终止顶点t离起始顶点s很远，需要遍历完整个图才能找到。此时每个顶点都要进出一遍队列，每个边也都会被访问一次。

所以广度优先搜索的时间复杂度是O(V+E)，V表示顶点的个数，E表示边的个数。
因为，对于一个连通图来讲，一个图中的所有顶点都是连通的，E肯定要大于等于V-1，所以广度优先搜索复杂度也可简写为O(E)。

BFS的空间复杂度

空间复杂度：广度优先搜素的空间消耗主要在几个辅助变量visited数组，queue队列，prev数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是O(V)。

深度优先搜索（DFS）

深度优先搜索（Depth-First-Search）简称。最直观的例子就是走迷宫。
深度优先搜素用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。

深度优先搜索代码实现也用到了prev，visited变量以及print()函数，作用于广度优先搜索代码实现里相同。但深度优先搜索代码实现里。有个比较特殊的变量found，他的作用是，当我们已经找到终止顶点t之后，我们就不再递归继续查找了。深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。

DFS的时间复杂度

时间复杂度：每条边最多会被访问两次，一次是遍历，一次是回退。所以DFS的时间复杂度是O(E)，E表示边的个数。

DFS的空间复杂度

空间复杂度：深度优先搜素算法的消耗内存主要是visited，prev数组和递归调用栈。Visited，prev数组的大小跟顶点的个数V成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是O(V)。

BF及RK算法

字符存储匹配算法是各种编程语言都会提供的字符匹配函数的底层依赖，它可以分为单模式匹配和多模式匹配算法。

单模式匹配：BF算法和RK算法，RK算法是BF算法的改进，它巧妙借助了哈希算法，提升了匹配的效率。

BF算法

BF算法是Brute Force的缩写，中文译作暴力匹配算法，也叫朴素匹配算法。
两个概念：主串和模式串

如在字符串A中查找字符串B，则字符串A就是主串，字符串B就是模式串
将主串长度记为n，模式串的长度记作m。因为是在主串中查找模式串，所以n>m

BF算法的思想可概括为：我们在主串中，检查起始位置分别是0,1,2……n-m且长度为m的n-m+1个子串，看有没有更模式串匹配的。

4. 极端情况下，如主串是“aaaaa…aaaaa”，模式串是“aaaab”。每次都比对m个字符，要比对n-m+1次，所以最坏的时间复杂度是O(m*n)。

虽然BF算法时间复杂度很高，但在实际开发中使用的非常常见。
- 原因1：实际软件开发中，大部分情况下，模式串和主串的长度都不会太长。每次模式串与主串中的子串匹配时，当中途不能遇到匹配的字符的时候，就可以停止，不需要全部对比一次。所以理论上最坏情况时间复杂度是O(m*n)，但这更多的是统计意义上的，大部分情况中，这个算法执行的很高效。
- 原因2：朴素字符串匹配算法思想简单，代码实现也非常简单，简单就意味着不容易出错。工程中，在满足性能要求的前提下，简单是首选，也是常说的KISS（keep it Simple and Stupid）设计原则。

RK算法：

RK算法的全称是Rabin-Karp算法，是两位发明人的名字拼接。是BF算法的升级版
BF算法的问题在于每次检查主串与子串是否匹配，需要依次对比每个字符，所以BF算法的时间复杂就比较高。但引入哈希算法，时间复杂度立即就会降低。
RK算法的思路：

通过哈希算法对主串中的n-m+1个子串分别求哈希值，

然后逐个于模式串的哈希值比较大小，如果相等就说明有对应的模式串。
4. 通过哈希算法计算字符的哈希值时，需要遍历子串中的每个字符，这只提供了模式串与子串比较的效率，但整体的效率并没有提高。
5. 为了提高哈希算法计算子串哈希值的效率，可以通过哈希算法的设计来解决。
假设要匹配的字符串的字符集中只包含k个字符，这就可以用一个k进制数来表示一个子串，这个k进制数转化成十进制，作为子串的哈希值。
6.
7. 这种哈希算法有个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。
8. 相邻额哈希值计算公式有交集：

9. 这个计算过程中，26m-1这部分的计算，我们可以通过查表的访求来提高效率。我们事物计算好 26^0、26^1、26^2、26^3…26^m-1，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。这样直接从数组中取值，从而省去了计算时间。

10. RK算法的时间复杂度：
1. 整个RK算法包含两个部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
2. 第一部分，只需要扫描一遍主串就能计算出所有子串的哈希值了，复杂度是O(n)。
3. 模式串哈希值与每个子串哈希值之间的比较时间复杂度是O(1)，总共需要比较n-m+1个子串的哈希值，所有，这部分的时间复杂度也是O(n)。
所以RK算法整体时间复杂度就是O(n)。
11. 如果模式串很长，相应的主串中子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整形数据可以表示范围，该如何解决？
答：我们可以把字符串中每个字母的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多。
12. 若出现哈希冲突如何解决？
答：如果两值相等，比较子串中每个字符。

所以，哈希算法中的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致RK算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要对比子串和模式串本身，时间复杂度就会退化成O(n*m)。

BM算法

BM（Boyer-Moore）算法，是一种非常高效的字符匹配算法，有实验统计他的性能是著名的KMP算法的3到4倍。BM算法的原理复杂

BM算法的核心思想

将模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF算法和RK算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。

BM算法，本质上就是在寻找当模式串不匹配时，可以将模式串往后多滑动几位多的规律，提高匹配的效率

BM算法原理分析

BM算法包含两部分，分别是

坏字符规则（bad character rule）
好后缀规则（good suffix shift）

坏字符规则：

在BF，RK规则中，在匹配的过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯。
BM算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配

3. 从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候，这个没有匹配的字符叫做坏字符（坏主串的字符）。
4. 坏字符c在模式串中查找，发现模式串中并不存在这个字符，即，字符c与模式串中的任何字符都不可能匹配。这个时候就可以将模式串直接往后滑动三位，将模式串滑动到c后面的位置，再次从模式串的末尾字符开始比较。

5. 这次发现模式串中最后一个字符d，还是无法跟主串中a匹配，但此时不能将模式串往后滑动三位。因为坏字符a在模式串中是存在的，模式串中下标是0的位置也是字符a。

当反生不匹配时，我们把坏字符对应的模式串中的字符下标记作si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作xi。如果不存在记作-1。模式串往后移动的位数就等于si-xi。

7. 利用坏字符规则，BM算法在最好情况先的时间复杂度非常低，是O(n/m)。
8. 不过，单纯使用坏字符规则还是不够得，因为根据si-xi计算出来的移动位数，有可能是负数，如主串是aaaaaaaaaaaaaaaa，模式串是baaaa。不但不会向后滑动模式串，还有可能倒退。所以BM算法还需要用到“好后缀规则”。

好后缀规则

好后缀规则实际上跟坏字符规则的思路很类似。

2. 将已经匹配的bc叫做好后缀，记作{u}。我们那它在模式串中查找，如果找到了另一个跟{u}相匹配的字串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

3. 但模式串中不存在等于{u}的子串时，不能直接将模式串滑动到主串{u}的后面。因为这会导致错过模式串和主串可以匹配的情况。

4. 如果好后缀在模式串中不存在可匹配的子串，那么一步步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有重合的时候，并且重合的部分相等的时候，就可能存在完全匹配的情况。

所以，针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

所谓某个字符串s的后缀子串，就是最后一个字符跟s对齐的子串，比如abc的后缀子串就包括c，bc。所谓前缀子串，找一个最长并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置。

好后缀和坏字符选用标准

1. 可以分别计算好后缀和坏字符往后滑动的位数，然后取两个中最大的，作为模式串往后滑动的位数。
2. 如果上面两种情况都不满足，那我们就需要将模式串向后移动到好后缀后面的位置。
复制代码

BM算法代码实现

“坏字符规则”本身不难理解。当遇到坏字符时，要计算往后移动的位数si-xi，其中xi的计算是重点，该如何查找坏字符在模式串中国出现的位置呢？
如果那坏字符，在模式串中顺序遍历查找，效率低下影响整个算法的性能。使用散列表将模式串中的每个字符及其下标都存在散列表中。这样就可以快速找到坏字符在模式串中的位置了。

3. 好后缀的处理规则中最核心的内容：
+ 在模式中，查找跟好后缀匹配的另一个子串；
+ 在好后缀的后缀子串中，查找最长的，能跟模式前缀子串匹配的后缀子串；
4. 引入 suffix 数组，其下标表示后缀子串的长度，而数组里面存储的是与这个后缀子串匹配的另一个子串在模式串中的起始位置。引入另外一个布尔型数组 prefix，来记录模式串的后缀子串是否能匹配其前缀子串。

我们拿模式串中下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度为 k，那我们就记录 suffix[k] = j（j 表示公共后缀子串的起始下标）。如果 j=0，也就说公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。

我们把 suffix 数组和 prefix 数组的计算过程，用代码实现出来，就是下面这个样子：

// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后缀子串长度
    while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
    }
    i
    if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
  }
}
复制代码

按如下步骤进行匹配判断：
- 先是匹配整个好后缀是否在模式串中存在，如果存在就后移到这个模式串相同的位置，匹配的方法就是suffix[k] 是否不等于 -1
- 若整个好后缀不存在，则匹配好后缀子串是否满足有可匹配的前缀子串，匹配方法就是看prefix[k] 是否等于 true
- 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。

代码实现如下：

// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后缀的话
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}
 
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}
复制代码

在不考虑效率的情况下，这两个操作都可以用“暴力”的匹配查找方式解决。但若要BM算法的效率高，需要：

因为好后缀也是模式串本身的后缀子串，所以，可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串。对应的另一一个可匹配子串的位置。

KMP算法

KMP在学习过程中觉得这两篇讲得更好
从头到尾彻底理解KMP
怎么理解kmp算法中的next数组?

Sunday算法

Sunday算法的思想和BM算法中的坏字符思想非常类似。
差别只是在于Sunday算法在失配之后，是取目标串中当前和模式串对应的部分后面一个位置的字符来做坏字符匹配。

BM算法和Sunday快速字符串匹配算法
 字符串匹配算法之Sunday算法

 【模式匹配】之 —— Sunday算法

Trie树

什么是“Trie树”？

他是一种树形结构，是一种专门处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的问题。
Trie树的本质是利用字符串之间公共前缀，将重复的前缀合并在一起。其中，根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点并不都是叶子节点）。
当在Trie树中查找一个字符串时，如“her”,就将要查找的字符串分割成单个的字符h，e，r，然后从Trie树的根节点开始匹配。但是假若要查找的字符串是“he”，用上面同样的方法，从根节点开始，沿着某条路径来匹配，发现路径的最后一个节点“e”不是红色的，即“he”是某个字符串的前缀，但不能完全匹配任何字符串。

如何实现一课Trie树？

Trie树主要有两个操作，一个是将字符串集合构造成Trie树。这个程可分解为：

将一个字符串插入到Trie树的过程
在Trie树中查询一个字符串

如何存储一个Trie树

Trie树是一个多叉树，需要存储一个节点的所有子节点的指针。
一种经典的存储方式：借助散列表额思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。

假设字符串中只有从a到z这26个小写字母，从数组中下标为0的位置，存储指向子节点a的指针，下标为1的位置存储指向子节点b的指针，以此类推，下标为25的位置，储存的是指向的子节点z的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储null。
当在Trie树中查找字符串的时候，就可以通过字符的ASCII码减去“a”的ASCII码，迅速找到匹配的子节点的指针。

Trie树查找的时间复杂度

在一组字符串中，频繁的查询某些字符串，用Trie树非常高效。
构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n) n表示所有字符串的长度和。但一旦构建成功后，后续的查询操作会非常高效。

每次查询，如果要查询的字符长度是k，那只需要对比大约k个节点。就能完成查询操作。与原本那组字符串的长度和个数没有任何关系。所以，构建好Trie树后，在其中查找字符串的时间复杂度是O(k)。k表示要查找字符串的长度。

Trie树很耗内存吗?

Trie树是使用数组来储存一个节点的子节点的指针的，即便一节点只有很少的子节点，远小于26个，比如2，3个，也要维护一个长度为26的数组。
Trie的本质是避免重复存储一组字符串的相同前缀子串，但现在每个字符（对应一个节点）的存储远远大于1个字节。
如果字符串中不仅包含小写字母，还包含大写字母，数字，甚至是中文，那需要的存储空间就更多了。所以在重复前缀并不多的情况下，Trie树不但不节省内存，还有可能浪费更多的内存。

Trie树的优化方案

牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点指针。如：有序数组，跳表，散列表，红黑树等。假设用有序数组，数组中的指针按照指向的子节点中的字符大小顺序排序。查询时，可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。
缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此子节点合并。这样可以节省空间，但却增加了编码难度。

Trie数与散列表的，红黑树的比较

字符串的匹配问题，笼统上讲，其实就是数据的查找问题。
在一组字符串中查找字符串，Trie数实际上表现的并不好，他对要处理的字符串有极其严苛的要求
- 字符中包含的字符集不能太大，如果字符集太大，那么存储空间就可能浪费很多。即便优化也要付出牺牲查询，插入效率的代价。
- 要求字符串的前缀重合比较到，不然空间消耗会变大很多。
- 如果要用Trie树解决问题，就需要自己从零开始实现一个Trie树，还要保证没有bug，这在工程上是把简单问题复杂化。
- 通过指针串起来的数据是不连续的，而Trie树用到了指针，所以，对缓存并不友好。性能上会打个折扣。

综上：Trie树不适合精确匹配查找，这种问题更适合用散列表或红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。

Trie的这个特点可以扩展到更加广泛的一个应用上：自动输入补全。

AC自动机

《轻松掌握ac自动机》
这个视频讲的挺好的，ac自动机感觉就是Tire树+KMP

单模式串匹配：

BF： 简单场景，主串和模式串都不太长, O(m*n)
**KP：**字符集范围不要太大且模式串不要太长，否则hash值可能冲突，O(n)
**naive-BM：**模式串最好不要太长（因为预处理较重），比如IDE编辑器里的查找场景；预处理O(m*m), 匹配O(n)，实现较复杂，需要较多额外空间。PS：如果用动态规划思想优化预处理算法，模式串长度的瓶颈会得到很大缓解。
**KMP：**适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快，原因不明.
另外查资料的时候还看到一种比BM/KMP更快，且实现+理解起来都更容易的的Sunday算法，有兴趣的可以看这里:

字符串匹配算法之Sunday算法

多模式串匹配：

naive-Trie: 适合多模式串公共前缀较多的匹配(O(n*k)) 或者根据公共前缀进行查找(O(k))的场景，比如搜索框的自动补全提示.
AC自动机: 适合大量文本中多模式串的精确匹配查找, 可以到O(n).