堆，图，字符串匹配算法超详细讲解


阅读数: 次   

概述

此博文将详细介绍三个模块的相关知识点，第一个模块是堆，其中包括堆的定义和实现以及堆的应用；其次是关于图，介绍图的定义及相关概念，图的存储，以及两种搜索算法 BFS 和 DFS；最后介绍字符串匹配算法，分别BF,RK

​ [泰国”Wat Sampran”龙庙]

堆

1.定义

堆其实是一棵树，并且是一种特殊的树。 其实只要满足以下两个要求它就是一个堆：

  1. 堆是一个完全二叉树；
  2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

第一点要求堆是一个完全二叉树，对于完全二叉树除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列，当然想到完全二叉树我们立马能能够想到我们之前所讲到的， 完全二叉树可以用数组来进行存储，之前的树每个节点不仅要存储数据还要存储左右节点的指针，虽然比较符合我们的认知但毕竟消耗一些存储空间，但是完全二叉树就不一样了，比较适合用数组来存储，是非常节省存储空间的，单纯的通过数组的下标我们就可以找到一个节点的左子节点和右子节点。

第二点要求堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值，或者我们可以换一种表述方式：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

2.堆的存储结构

堆是一个完全二叉树，我们可以用数组来存储，用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

数组中下标为 k 的节点的左子节点，就是下标为 2k 的节点，右子节点就是下标为 2 k +1 的节点，父节点就是下标为 k/2 的节点，其中 k>=1。另外我们也发现，数组下标为 0 的位置并未存储数据，这是因为为了方便于在程序中计算，所以会浪费掉数组的一个存储空间。

3.堆的实现

3.1创建堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 创建一个存储堆中元素数组
private int[] data;
// 堆中存储元素最大个数
private int size;
// 堆中已经存储元素个数
private int count;
//定义哨兵大于堆中所有可能的元素值，方便后续操作
private final static int MAX = 1000;
/**
* 初始化
* @param cp
*/
public Heap(int cp) {
    data = new int[cp + 1];
    data[0] = MAX;
    size = cp;
    count = 0;
}

@Override
public String toString() {
    return "Heap [data=" + Arrays.toString(data) + ", size=" + size + ", count=" + count + "]";
}

3.2插入元素

我们往堆中插入元素就是向数组的数据末位添加值，也就是将新来的值放在堆的最后，前面我们已经知道了堆的特性，所以添加完成后要继续满足堆的两个特性，就需要继续进行调整，这个调整的过程我们叫做堆化。

方法一

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 将数据存入堆中
 * @param value
 */
public void insert(int value) {
	if(count>=size)return;//堆已满
	int i = ++count;
	for(;value>data[i/2];i/=2) {//这里到了最顶有哨兵来终结此循环
		data[i]=data[i/2];//自下而上堆化，上面的数据给到下面
	}
	data[i]=value;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 将数据存入堆中,
* @param data
*/
public void insert(int data){
    if(count >= size ){
    return;// 堆已满
    }
    // 将数据存入
    this.data[++count] = data;
    // 堆化：自下而上堆化
    heapifyFromBottom2Top(this.data,count);
}
/**
* 将数组 data 堆化
* @param data
* @param end 从 end 位置自下而上堆化
*/
private void heapifyFromBottom2Top(int[] data,int end){
    int i = end;
    while ( i/2 > 0 && this.data[i/2] < this.data[i]){
        swap(this.data,i/2,i);
        i /=2;
	}
}
/**
* 交换数组下标 i,j 的元素
* @param array
* @param i
* @param j
*/
public void swap(int[] array,int i,int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

3.3删除堆顶元素

我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法

因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树的特性

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 移除堆顶元素
 * @return
 */
public int removeMax() {
	if(count==0)return -1;//堆已空
	int max = data[1];
	int temp = data[count--];
	for(int parent=1;parent*2<=count;) {
		int child = parent*2;
		if(child!=count&&data[child]<data[child+1])child++;//child指向左右子节点的较大者
		if(temp>=data[child]) {
			data[parent] = temp;
			break;
		}
		else {
			data[parent] = data[child];//自上而下堆化，下面的数据给到上面
			parent = child;
		}
	}
	return max;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 移除堆顶元素
* @return
*/
public int removeMax(){
    // 如果是大顶堆,数组下标为 1 的元素就是最大值
    int max = data[1];
    //移除完成后要保证堆的完整，需要找第二大的元素放到堆顶
    //1: 将最后一个元素直接放在堆顶,并减少数量
    data[1] = data[count--];
    //2: 堆化让其继续成为一个合格的堆---->这个时候要自上而下堆化
    headifyFromTop2Button(data,1,count);
    return max;
}
/**
* 将数组 data 堆化
* @param data
* @param begin 从该位置自上而下堆化
* @param end 堆化截止位置
*/
private void headifyFromTop2Button(int[] data,int begin,int end){
    while (true){
        // 定义最大值的下标
        int maxPos = begin;
        // 比较当前节点与其左子节点,右子节点的大小关系,找出最大值
        if( 2*begin <= end && data[maxPos] < data[2*begin]){
        	maxPos = 2*begin;
        }
        if(2*begin+1 <=end && data[maxPos] < data[2*begin +1]){
        	maxPos = 2*begin +1;
        }
        if(begin == maxPos){
        	break;
        }
        swap(data,begin,maxPos);
        begin = maxPos;
    }
}

3.4时间复杂度分析

堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是O(logn)。插入数据和删除堆顶素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn) 。

4.堆的应用(堆排序)

借助于堆这种数据结构实现的排序算法，就叫作堆排序。这种排序方法的时间复杂度非常稳定，是 O(n*logn)，并且它还是原地排序算法。我们可以把堆排序的过程大致分解成两个大的步骤， 建堆和排序。

算法描述如下：

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  • 将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；
  • 由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

4.1建堆

如果给定一个数组，我们要把这个数组中的数据变成符合堆的数据存储，意味着将原始数据变成堆，并且我们是在原地将原始数据变成堆，所谓的原地操作也就是空间复杂度为 O(1)的操作，无需额外的内存空间即可完成。

第一种是借助我们前面讲的，在堆中插入一个元素的思路。尽管数组中包含 n 个数据，但是我们可以假设，起初堆中只包含一个数据，就是下标为 1 的数据。然后，我们调用前面讲的插入操作，将下标从 2 到 n 的数据依次插入到堆中。这样我们就将包含 n 个数据的数组，组织成了堆，这里面的堆化操作是属于自下而上的堆化操作。

第二种实现思路，跟第一种截然相反，第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点开始，依次堆化就行了，那第一个非叶子节点如何找呢？别忘记堆是一个完全二叉树，堆中最后一个元素下标除以 2 取整就是第一个非叶子节点的下标位置。

我们这里用第二种实现

1
2
3
4
5
6
7
8
9
10
11
/**
 * 建堆：建大顶堆,堆化是自上而下堆化
 * @param data
 * @param n	数组最后一个元素的下标---堆中最后一个元素下标
 */
private void buildHeap(int[] data,int n) {
	//从后往前处理数组数据,堆化的时候是自上而下堆化
	for(int i=n/2;i>0;i--) {
		heapifyT2B(data, i, n);
	}
}

从代码的实现逻辑上我们发现，我们对下标从 k/2 开始到 1 的数据进行堆化，下标是 k/2+1 到 k 的节点是叶子节点，我们不需要堆化。实际上，对于完全二叉树来说，下标从 k/2+1 到 k 的节点都是叶子节点。首先每个节点堆化的复杂度是O(logn),我们堆化了大约n/2+1个结点，所以时间复杂度是O(n*logn)。

4.2排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 堆排序：分为两步
 * 1：建堆
 * 2：排序
 * @param data
 */
public void heapSort(int[] data) {
	//1.建堆
	buildHeap(data, data.length-1);
	//2.排序
	sort(data, data.length-1);
}
/**
 * 排序：
 * 我们把堆顶元素跟最后一个元素互换,然后对 1~n-1 区间的元素再堆化,然后在将堆顶元素跟最后一个元素互换继续操作
 * @param data
 * @param n
 */
private void sort(int[] data,int n) {
	while(n>1) {
		swap(data, 1, n);
		heapifyT2B(data, 1, n--);
	}
}

4.3复杂度分析

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是O(n*logn) ，所以，堆排序整体的时间复杂度是O(n*logn)。堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

图

1.概念

图中的每一个元素我们称之为顶点（ Vertex） ，并且图中的一个顶点可以与其他任意顶点建立连接关系，我们把这种建立的关系叫做边(Edge)，

实际上，生活中的社交网络就是一个非常典型的图的结构，比如微博，微信， qq，每个人都有好友，可以互相关注，等等。

我们就拿微信举例子吧。我们可以把每个用户看作一个顶点。如果两个用户之间互加好友，那就在两者之间建立一条边。所以，整个微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree） ，就是跟顶点相连接的边的条数。

+++

实际上，微博的社交关系跟微信还有点不一样，或者说更加复杂一点。微博允许单向关注，也就是说，用户 A 关注了用户 B，但用户 B 可以不关注用户 A。那我们如何用图来表示这种单向的社交关系呢？

我们可以把刚刚讲的图结构稍微改造一下，引入边的“方向”的概念。如果用户 A 关注了用户 B，我们就在图中画一条从 A 到 B 的带箭头的边，来表示边的方向。如果用户 A 和用户 B 互相关注了，那我们就画一条从 A 指向 B 的边，再画一条从 B 指向 A 的边。我们把这种边有方向的图叫作“有向图”。以此类推，我们把边没有方向的图就叫作“无向图”。

在有向图中，我们把度分为入度（In-degree）和出度（ Out-degree） 。

顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。

QQ 中的社交关系要更复杂的一点。不知道你有没有留意过QQ 亲密度这样一个功能。 QQ 不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度，如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。如何在图中记录这种好友关系的亲密度呢？

这里就要用到另一种图， 带权图（ weighted graph） 。在带权图中，每条边都有一个权重（weight） ，我们可以通过这个权重来表示 QQ 好友间的亲密度。

2.图的存储方式

其实图有很多中存储形式包括：邻接矩阵，邻接表，十字链表，邻接多重表，边集数组等等，在今天我们主要讲解其中的两种存储：邻接矩阵和邻接表

2.1邻接矩阵存储图

邻接矩阵存储图底层依赖一个二维数组，对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i]标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j]标记为 1同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i]标记为 1。对于带权图，数组中就存储相应的权重。

linjie

对于使用邻接矩阵来存储图的特点是：简单，直观。但是也有一定的缺点就是浪费存储空间，比如对于上面图示的情况来看第一种无向图的存储， A[i] [j]等于 1 那么 A[j] [i]也等于 1，在那个二维数组中我们沿着对角线划分为上下两部分，两部分其实是对称的，其实我们只需要一半的存储空间就够了，另一半算是浪费了。

适用场景：使用于稠密的图，可以快速定位到指定的边，但是如果是稀疏的图，会比较浪费空间

2.2邻接表存储图

每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

使用邻接矩阵存储图的好处是直观简单方便，但是缺点是浪费存储空间，相反的邻接表存储图的好处就是比较节省存储空间，但是缺点就是时间成本教高。

如果我们要确定，是否存在一条从顶点 2 到顶点 4 的边，那我们就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。在散列表那几节里，我讲到，在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。我们刚刚也讲到，邻接表长得很像散列。所以，我们也可以将邻接表同散列表一样进行“改进升级”。

我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然，这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。除此之外，我们还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

lnjiebiao

一个邻接表来存储这种有向图是不够的,我们在某些场景下需要知道哪些顶点指向这个顶点，如你想知道你在B站的粉丝，这时候我们需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找某个用户关注了哪些用户，我们可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，我们从逆邻接表中查找。

3.图的应用-搜索算法

3.1定义图的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//图中顶点个数
private int points;
// 邻接表: 有点类似散列表,数组每个槽位链表头节点存储的是图中的顶点,链表其他节点存储的是与该顶点相连的顶点
private LinkedList<Integer>[] adjacencyList;

public UndiGraph(int points) {
	this.points = points;
	adjacencyList = new LinkedList[this.points];
	for(int i=0;i<this.points;i++) {
		adjacencyList[i] = new LinkedList<>();
	}
}
/**
 * 向图中添加顶点(边)
 * @param s
 * @param t
 */
public void addEdges(int s,int t) {
	// 无向图,一条边存储两回;注意：在该案例中,无向图中存储的顶点的值和数组的下标值保持对应
	adjacencyList[s].add(t);
	adjacencyList[t].add(s);
}

3.2广度优先搜索 BFS

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法，直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

这里我强烈推荐一个博主写的广度优先搜索算法，他详细的分析了广度优先搜索算法解决的问题和步骤，还有为什么我们在此算法中需要用队列来存储顶点，我在此简要概括一下，想详细了解的同学直接点击连接。

广度优先搜索可回答两类问题：

第一类问题：从节点A出发，有前往节点B的路径吗？

第二类问题：从节点A出发，前往节点B的哪条路径最短？

广度优先算法可以理解为你找朋友帮一个技术性的忙，你先找你的朋友，如果找到就结束，找不到，你就需要找你朋友的朋友，然后循环下去，直到找到为止。这里你肯定需要先把你的朋友全找完，再去找你朋友的朋友，所以我们需要一个的队列，因为队列可以从尾部插入，从头部抛出，先找你的朋友，帮不了忙就把你朋友的朋友加入队尾，然后依次循环，这样第一个找到的肯定是跟你关系最近的。

+++

算法步骤：

  1. 首先将源顶点放入队列中。
  2. 从队列中取出第一个顶点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。
    否则将它所有尚未检验过的直接子顶点加入队列中。
  3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不
    到目标”。
  4. 重复步骤 2。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public void bfs(int source,int target) {
	if(source==target)return;
	// 定义一个 boolean 数组记录顶点是否被访问过
	boolean[] visited = new boolean[this.points];
	visited[source]=true;
	// 定义一个队列,BFS 算法借助了一个队列
	Queue<Integer> queue = new LinkedList();
	queue.add(source);
	// 定义一个数组，记录从源顶点到目标顶点之间的线路
	int[] pre = new int[this.points];
	for(int i=0;i<this.points;i++) {
		pre[i] = -1;
	}
	/**
	 * BFS算法核心思想
	 * 从队列中取出第一个顶点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子顶点加入队列中。
	 * 重复上面操作
	 */
	while(!queue.isEmpty()) {
		//取出顶点元素
		Integer p = queue.poll();
		//从邻接表中取出跟该顶点相连的顶点链表
		for(int j=0;j<adjacencyList[p].size();j++) {
			//依次取出顶点P相连的顶点
			Integer p_connect = adjacencyList[p].get(j);
			if(!visited[p_connect]) {
				//记录 p_connect 之前的顶点是 p
				pre[p_connect] = p;
				// 判断跟顶点 p 相连的顶点 p_connect 是否是目标顶点
				if(p_connect==target) {
					//打印从源顶点到目标顶点之间的线路
					print(pre, source, target);
					return;
				}
				// 标识顶点 p 已被访问
				visited[p]=true;
				// 将顶点 p 相连的顶点 p_connect 加入队列
				queue.add(p_connect);
			}
		}
	}
}

/**
 * 递归打印从 s 到 t 之间的线路
 * @param pre
 * @param s
 * @param t
 */
private void print(int[] pre,int s,int t) {
	if(pre[t]!=-1&&s!=t) {
		print(pre, s, pre[t]);
	}
	System.out.print(t+"->");
}

+++

时间复杂度分析：

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中， V 表示顶点的个数， E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的， E 肯定要大于等于 V-1，所以， 广度优先搜索的时间复杂度也可以简写为 O(E)。

空间复杂度：

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

3.3深度优先搜索 DFS

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

+++

实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 从源顶点到目标顶点的深度优先搜索 DFS
 * 	需要借助一个全局的变量来记录是否找到目标顶点
 * @param source
 * @param target
 */
private boolean found = false;
public void dfs(int source,int target) {
	if(source==target)return;
	boolean[] visited = new boolean[this.points];
	int[] pre = new int[this.points];
	for(int i=0;i<this.points;i++) {
		pre[i]=-1;
	}
	//递归调用
	recurDFS(source,target,visited,pre);
	//打印线路
	print(pre,source,target);
}
/**
 * 递归的查找顶点 p 到目标顶点之间的线路图
 * @param point
 * @param target
 * @param visited
 * @param pre
 */
private void recurDFS(int point,int target,boolean[] visited,int[] pre) {
	if(found)return;
	//标记当前结点已被访问
	visited[point]=true;
	//如果当前顶点就是目标顶点
	if(point==target) {
		found=true;
		return;
	}
	for(int j=0;j<adjacencyList[point].size();j++) {
		Integer p_connect = adjacencyList[point].get(j);
		if(!visited[p_connect]) {
			pre[p_connect]=point;
			//递归的去找与 p_connect 相连的顶点
			recurDFS(p_connect, target, visited, pre);
		}
	}
}

+++

时间复杂度分析：

可以看出，每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)， E 表示边的个数。

空间复杂度分析：

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

字符串匹配/查找算法

1.BF算法

1.1原理

BF 算法，即暴风(Brute Force)算法，也叫朴素匹配算法，是普通的模式匹配算法，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高，所以 BF 算法也是一种蛮力算法。

几个概念，方便后续的讲解：模式匹配，主串和模式串

模式匹配：即子串 P(模式串)在主串 T(目标串)中的定位运算，也称串匹配。假设我们有两个字符串：T(Target, 目标串，主串)和 P(Pattern, 模式串，子串)；在主串 T 中查找模式串 P 的定位过程，称为模式匹配。

模式匹配有两种结果：
• 主串中找到模式为 P 的子串，返回 P 在 T 中的起始位置下标值；
• 未成功匹配，返回-1

1.2代码

我们在主串中，检查起始位置分别是 0、 1、 2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class BF {
	/**
	 * 使用 bf 算法在主串 t 中匹配模式串 p
	 * @param t	主串/目标串
	 * @param p	模式串/子串
	 * @return	能匹配上则返回 p 在 t 中匹配的下标,匹配不上则返回-1
	 */
	public int bf(String t,String p) {
		if(t==null||t.length()==0||p==null||p.length()==0||p.length()>t.length()) {
			return -1;
		}
		char[] t_array = t.toCharArray();
		char[] p_array = p.toCharArray();
		return match(t_array, p_array);
	}
	
	private int match(char[] t,char[] p) {
		int i=0;// 主串下标
		int j=0;// 模式串下标
		int pos = 0;//匹配到的位置
		while(i<t.length&&j<p.length) {
			if(t[i]==p[j]) {
				i++;j++;//如果匹配则目标串和模式串进行下一个字符的匹
			}else {//如果匹配不成功，则从目标字符串的下一个位置开始从新匹配
				i = i-j+1;//这里i可能之前++过了，不能直接i++;i之前要是++必然伴随j++，这个公式可以完美算出刚刚没匹配的上的下一个字符位置
				j = 0;
			}
		}
		if(i<=t.length) {//可能一直没查到，这时候i=t.length+1，所以要判断一下
			pos = i-p.length;
		}else {
			pos = -1;
		}
		return pos;
	}
}

1.3时间复杂度分析

比如主串是“aaaaa…aaaaaa”（省略号表示有很多重复的字符 a），模式串是“aaaaab”。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(nm)。

尽管理论上， BF 算法的时间复杂度很高，是 O(nm)， n 是主串的长度， m 是模式串的长度，但在实际的开发中，它却是一个比较常用的字符串匹配算法。为什么这么说呢？原因有两点。

第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的 KISS（Keep it Simple and Stupid）设计原则。

2.RK算法

2.1原理

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。它是 BF 算法的升级版，主要在这个算法中引入了哈希算法。

我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串不相等，那这个字串和模式串必定不等，如果某个字串的哈希值与模式串的哈希值相等，则该字串与模式串不一定相等，因为有哈希冲突的存在，如果出现了哈希冲突后我们可以采用 BF 算法思想对该子串和模式串进行暴力匹配；因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

这就需要我们设计良好的哈希函数，我们假设要匹配的字符串的字符集中只包含 R个字符，我们可以用一个 R 进制数来表示一个子串，这个 R 进制数转化成十进制数，作为子串的哈希值。

比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。

十进制：657=6 10 10 + 5 * 10 + 7

二十六进制：cba= c 26 26 + b 26 + a=2 26 26 + 1 26 +0

这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系

相邻两个子串 s[i-1] 和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，我们可以使用 s[i-1] 的哈希值很快的计算出 s[i] 的哈希值。

通过上面的分析我们可以将一个字符串看成 R=26 进制的数，这样在比较的时候比较其换算成十进制后的数字，但是可能一个 26 进制的数换算成 10 进制后太大，甚至有可能超过了 java 中 int 类型的范围，那这时该如何处理呢？我们还可以借助另一个哈希函数，取模运算。

取模运算： “%”, hash = key % M，其中 M 一般是素数，否则可能无法利用 key 中包含的所有信息。如 key 是十进制数而 M 是 10 的 k 次方，那么只能利用 key 的后 K 位，不均匀， 增加碰撞概率。

2.2代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class RK {

	/**
	 * 使用 bf 算法在主串 t 中匹配模式串 p
	 * 
	 * @param t
	 *            主串/目标串
	 * @param p
	 *            模式串/字串
	 * @return 能匹配上则返回 p 在 t 中匹配的下标,匹配不上则返回-1
	 */
	public int rk(String t, String p) {
		if (t == null || t.length() == 0 || p == null || p.length() == 0 || p.length() > t.length()) {
			return -1;
		}
		int phash = hash(p, 26, 31, 0, p.length());
		for (int i = 0; i < t.length() - p.length() + 1; i++) {
			if (hash(t, 26, 31, i, p.length()) == phash && match(t, p, i)) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 求一个字符串的哈希值
	 * 
	 * @param str
	 * @param R
	 *            对应的进制
	 * @param K
	 *            将字符串映射到 K 的范围内
	 * @param start
	 *            从 str 串的 start 位置开始
	 * @param len
	 *            模式串的长度 len
	 * @return
	 */
	private int hash(String str, int R, int K, int start, int len) {
		int hash = 0;
		for (int i = start; i < start + len; i++) {
			hash = (R * hash + str.charAt(i)) % K;
		}
		return (hash % K);
	}

	/**
	 * 当连个字符串的 hash 一样时则表明哈希冲突了,hash 值一样两个串不一定一样,需要再依次比较一下
	 * 
	 * @param t
	 * @param p
	 * @param i
	 *            从主串下标为 i 的地方开始比较
	 * @return
	 */
	private boolean match(String t, String p, int i) {
		for (int j = 0; j < p.length(); j++) {
			if (p.charAt(j) != t.charAt(j + i))
				return false;
		}
		return true;
	}
}

2.3时间复杂度分析

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 nm+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以， RK 算法整体的时间复杂度就是 O(n)。跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。

结语

悲剧的少年为何频繁惨死？
飞机场的幼女为何有沟？
傲娇的女主为何报上假名？
高大上的剑圣为何搞基？
罗姆爷关爱幼女的背后又隐藏着什么？
蓝毛和红毛为什么要这样虐男主？
这一切的背后！！！是人性的扭曲，还是道德的沦丧？是偶然的失足，还是命运的安排？

敬请关注从零开始的异世界。仰慕凄惨的男主吧！

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家