kmp算法
kmp算法
kmp是一种高效存储字符串匹配的算法
关键:在主串中找模板串的位置
遇到两个字符不匹配的情况时,希望可以多跳几个字符,减少比较次数。KMP算法的思想是:在模式串和主串匹配过程中,当遇到不匹配的字符时,对于主串和模式串中已对比过相同的前缀字符串,找到长度最长的相等前缀串,从而将模式串一次 ...
Trie字符串统计
Trie字符串统计
存储字符串,快速存储字符串集合
高效存储和查找
特点:字母的个数不会很多
以单词的结尾要标记,用星号标记
定义子节点son[N][26] 存的是每个点的儿子 cnt[N] ,以当前这个点结尾的下标有多少个,idx当前用到了那个下标
模板
int son[N][26], ...
单调队列
单调队列
场景: 滑动窗口,经典问题
模板
常见模型:找出滑动窗口中的最大值/最小值int hh = 0, tt = -1;for (int i = 0; i < n; i ++ ){ while (hh <= tt && check_out(q[hh ...
单调栈
单调栈
情景: 最常用:给定一个序列,找到序列每一个数左边离它最近且比他小的数
例如:
3 4 2 7 5
-1 3 -1 2 2
思路:一般先找暴力做法,然后优化
优化的思路:可以用一个栈来存储,
a_3 a_5 a_i
假设 a_3 >= a_5
a_ ...
模拟队列
模拟队列
用数组模拟队列
队列的特点:先进先出
模板
普通队列
// hh 表示队头,tt表示队尾int q[N], hh = 0, tt = -1;// 向队尾插入一个数q[ ++ tt] = x;// 从队头弹出一个数hh ++ ;// 队头的值q[hh];// 判断队列是否为空if ( ...
模拟栈
模拟栈
栈是比较简单的,用数组模拟
栈的特点:后进先出
模板
// 几个操作 入栈,出栈,查询栈顶,判断是否为空// tt表示栈顶int stk[N], tt = 0;//1. 入栈stk[++tt] = x;//2. 出栈tt --;//3. 查询栈顶stk[tt];//4. 判断是否为空i ...
双链表
双链表
双链表和单链表的区别:双链表是左右都有的
l[N], r[N]
再双链表中,我们用0表示头节点,1,表示尾点
双链表的几个基本操作:
插入一个点,左插入,有插入
模板
int e[N], l[N], r[N], idx;void init(){ //0 表示左端点 ...
单链表
单链表
用数组模拟单链表 用数组效率高
单链表:领接表 应用:存储图和树
双链表: 优化某些题
单列表:直往后看,不往前看
单链表的几个基本操作:
插入头部
插入第k个数之后
删除第k个点
用下标来关联,空数组的下标是-1
模板
//head 表示头节点的下标//e[i] 表示节点i ...
区间合并
区间合并
输入区间:按照左端点排序
模板
void merge(vector<PII> &segs){ vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, e ...
离散化
离散化
离散化的两个核心问题:
数组中可能有重复元素 – 去重
快速映射,算出a[] 离散化的值
模板
vector<int> alls; // 存储所有待离散化的值sort(alls.begin(), alls.end()); // 将所有值排序//alls.erase( ...