type
status
date
slug
summary
tags
category
icon
password
@ZZHow(ZZHow1024)
字符串
KMP字符串
致敬三位前辈：D.E.Knuth、J.H.Morris 和 V.R.Pratt！
字符串模式匹配算法，大大避免重复遍历的情况，克努特-莫里斯-普拉特算法。
Trie树
用于高效地存储和查找字符串集合的数据结构。
并查集
两个操作：
- 将两个集合合并。
- 询问两个元素是否在一个集合当中。
基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储
它的父节点，P[x] 表示 x 的父节点。
问题 1：如何判断树根
if (p[x] == ×) {return true;}
问题 2：如何求 x 的集合编号 while (p[x] != x) x = p[x];
问题 3：如何合并两个集合，p[x] 是 x 的集合编号，p[y] 是 y 的集合编号 p[x] = y;堆
手写堆，功能：
- 插入一个数：
heap[++size] = x; up(size);
- 求集合中的最小值：
heap[1];
- 删除最小值：
heap[1] = heap[size]; size--; down(1);
- 删除任意一个元素：
heap[1] = heap[k]; size--; down(1); up(1);
- 修改任意一个元素：
heap[k] = x; down(k); up(k);
使用一维数组存储：
- x 左儿子：2x
- x 右儿子：2x + 1