左神算法基础提升--2

岛问题

求解这个问题时我们可以使用渲染的方式，我们先从某个1出发，在其上下左右四个方向上进行递归，使得每一个部分都被遍历过，并将值为1的值渲染为2，后在每一部分递归结束后岛数量加一。


这是一个单核的解法。但是我们该如何设计一个并行的方法呢？
首先，并行的方法是指，我们设计一种算法，使得一个很大的数据量被分成好几份较小的数据分别进行计算，并在最终进行统筹得到一个结果。其中一个难点在于如何统筹较小的数据计算得到的结果，使其成为原问题的解，此时，我们便需要学习一种新的数据结构，并查集。

并查集

并查集原理

并查集是一种非常高效的数据结构，主要用于处理一些不交集的合并及查询问题。

1. 基本概念

集合：并查集将元素组织成若干个不相交的集合，每个集合代表一个连通块。
根节点：每个集合用一个树状结构表示，树的根节点是该集合的代表元素，通常用来唯一标识一个集合。

2. 初始化

对于有n个元素的集合，在初始化阶段，要求用户将全部节点交给并查集，并查集会将每个元素成为一个独立的集合，即每个元素的父节点指向自己，用一个哈希表fatherMap来表示，同时将每个集合的节点数量定义为1。

3. 查找（Find）

目的：确定元素所属的集合，即找到元素所在树的根节点。
过程：
从给定元素开始，沿着父节点指针向上查找，直到找到根节点，并使用一个栈将其父节点加入到栈中。并采用路径压缩技术，将查栈中点都直接指向根节点。这样可以使得树的高度降低，后续查找操作更加高效。

4. 合并（Union）

目的：将两个元素所属的集合合并成一个集合。
过程：
首先通过查找操作找到两个元素各自所在集合的根节点。
比较两个元素所在集合的节点个数，将较小根节点的父节点指向另一个根节点，从而将两棵树合并成一棵树，实现集合的合并，在之后更新大集合的节点个数并删除小集合。

回归岛问题

以下图为例，我们需要在一个大范围的数据集中找到有多少个岛。我们先将这个大数据集划分为两个子问题，分别求出两个子问题各自有多少个岛，以下图为例，两个子问题均存在两个岛。

之后我们需要使用并查集的知识将，将结果统筹起来。我们先找到初始渲染点以及边界中被其渲染的点，将他们记为同一个集合，如下图所示：

如果边界相碰的形式，便将这两个边界点所对的集合合并并减少一个岛的数量

当所有边界均被判定后，最终的岛的数量便是最后的结果。

KMP算法

经典算法

我们使用经典的思想求解这道题时，是使用两层for循环尝试str1的每一个开头能不能配出str2的思想解决，这样的代码简单易懂，但其所需的时间就非常的多了。

以上图为例，上图中在第一次进行判断时，我们比对了m（str2的长度）个位置但却只能认为只有第一个开头不能配出，不断循环下去。最终我们能得出其时间复杂度为O（n*m）.为了更加节省时间，我们便可以使用KMP算法进行求解。

最长相同前后缀的长度

在学习KMP算法之前，我们需要了解什么是最长相同前后缀长度

其含义在于，找到在一个点之前的字符串其最长相通的前后缀长度，以上图为例，上图中最长相同前后缀长度为3.

在使用KMP算法之前，我们需要对str2求解出其每个字符的最长相通的前后缀长度作为str2的next数组，有了这部分我们便可以使用KMP算法对判断过程进行加速。

KMP算法的加速原理

在经典算法中我们如果比对到一个不一样的数（X,Y）我们需要将x=x+1,y=0.但KMP算法不同，KMP算法，在比对到不相等的数时，其会让x保持不变，让y=next[y],这样便极大的减少了重复计算的过程，使所需时间大幅度减少。
其能这样操作的实质在于在之前进行比对时，已经比对过了部分内容。

代码