匹配_KMP模式匹配算法：一
模式匹配 对子串的定位操作通常被称为串的模式匹配 简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止 朴素的...
数据结构模板
单链表 // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { h...
匹配_Rabin_karp匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,.....
排序_插入排序
简述 插入排序思想，假设对数组A[p...r]排序: 维持不变式：设当前排序的元素是 A[q]，则保持A[p...q-1]为排好的，A[q]在A[p...q-1]中找到它的位置坐下 复杂度 O(n^2) 原地排序 实...
数学知识模板
试除法判定质数 bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i =...
匹配_KMP模式匹配算法：二
预处理操作 参数 iterP_begin:模式序列P的起始迭代器 iterP_end:模式序列P的终止迭代器 解析 初始化 pai[1] = 0,k = 0 遍历(q从：2->m) 从2开始，因为Pk必须是Pm...
搜索与图论模板
树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 邻接矩阵：g[a][b] 存储边a->b 邻接表：...
匹配_有限自动机字符串匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,.....
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述...
动态规划相关
概述 动态规划（Dynamic Programming，简称 DP）是一种通过分解问题来解决复杂问题的算法技术，特别适用于具有最优子结构性质的问题，即问题的最优解可以由其子问题的最优解构建而成 动态规划的核心思想是将...