五、单调栈
核心模板
//常见模型：找出每个数左边离它最近的比它大/小的数 int tt=0; for(int i=1;i<=n;i++){ while(tt&check(s[tt],i)) tt--; s[++tt]=i; }
题目链接：830. 单调栈
5.1题目描述
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：
5 3 4 2 7 5
输出样例：
-1 3 -1 2 2
5.2思路分析
暴力求解：
每次i循环都将i前面的数入栈（从1到i-1元素入栈）
单调栈优化：
在暴力算法基础上，如果存在离目标值近的且小于目标值的x，且存在一个也离目标值近但是没有x离目标值近且没有x小的y，则可以去掉y（y不会被用到，因为x比y更优，将y出栈），使栈中元素为 单调上升 的序列。
5.3代码实现
#include <iostream> #include <cstdio> using namespace std; const int N=100010; int n; int s[N],tt; int main() { scanf("%d",&n); for(int i=0;i<n;i++){ int x; scanf("%d",&x); while(tt&&s[tt]>=x) tt--; //如果当前元素比栈顶元素小且下标比栈顶元素大，说明当前元素比栈顶元素更优，弹出栈顶元素 ;注意是while if(tt){ printf("%d ",s[tt]); } else{ printf("-1 "); } s[++tt]=x; //将当前元素入栈 } return 0; }
六、单调队列
核心模板
//常见模型：找出滑动窗口中的最大值/最小值 int hh=0,tt=-1; for(int i=0;i<n;i++){ while(hh<=tt&&check_out(q[hh])) hh++; //判断队头是否滑出窗口 while(hh<=tt&&check(q[tt],i)) t--; q[++tt]=i; }
题目链接：154. 滑动窗口
6.1题目描述
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3 1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3 3 3 5 5 6 7
6.2思路分析
最小值（用 队列 维护）：如果存在在窗口中存在最小值，而且在最小值位置之前存在比它大的数，则这些数一定不会作为答案输出，可以去掉，即使队列中的元素始终是 单调上升 的。
最大值求法类似。
6.3代码实现
#include <iostream> using namespace std; const int N=1000010; int n,k; int a[N],q[N]; //q[]模拟队列，存储下标 int main() { cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]; } //求最小值 int hh=0,tt=-1; for(int i=0;i<n;i++){ //判断队头是否已经滑出窗口 if(hh<=tt&&i-k+1>q[hh]){ hh++; } //如果队尾元素比当前元素大，则去掉队尾元素 while(hh<=tt&&a[q[tt]]>=a[i]){ tt--; } q[++tt]=i; //把当前元素下标入队 if(i>=k-1){ cout<<a[q[hh]]<<" "; } } cout<<endl; //求最大值 hh=0,tt=-1; for(int i=0;i<n;i++){ //判断队头是否已经滑出窗口 if(hh<=tt&&i-k+1>q[hh]){ hh++; } //如果队尾元素比当前元素小，则去掉队尾元素 while(hh<=tt&&a[q[tt]]<=a[i]){ tt--; } q[++tt]=i; //把当前元素下标入队 if(i>=k-1){ cout<<a[q[hh]]<<" "; } } return 0; }
七、KMP算法
核心模板
//s[]是长文本，p是模式串，n是s的长度，m是p的长度 //求模式串的next数组： for(int i=2,j=0;i<=m;i++){ while(j&&p[i]!=p[j+1]) j=ne[j]; if(p[i]==p[j+1]) j++; ne[i]=j; } //匹配 for(int i=1,j=0;i<=n;i++){ while(j&&s[i]!=p[j+1]) j=ne[j]; if(s[i]==p[j+1]) j++; if(j==m){ j=ne[j]; //匹配成功后的逻辑 } }
题目链接：831. KMP字符串
7.1题目描述
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出 模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0开始计数），整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例：
3 aba 5 ababa
输出样例：
0 2
7.2思路分析
暴力做法：
KMP算法：
next数组：
next[i]=j表示字符串前i个字母中从第一个字符开始长度为j的字符串与从某个位置到结尾长度为j的字符串相等，而且此长度j为最大（最长相等前后缀的长度）。
7.3代码实现
#include <iostream> using namespace std; const int N=100010,M=1000010; int n,m; char p[N],s[M]; int ne[N]; int main() { cin>>n>>p+1>>m>>s+1; //求next过程 next[1]=0,因为j=1不匹配时只能退到j=0 for(int i=2,j=0;i<=n;i++){ //求next数组也是根据p串来找某个位置i的最长公共前后缀 while(j&&p[i]!=p[j+1]){ //如果j没有退回起点而且当前p[i]和p[j+1]不匹配 j=ne[j]; //j退回到可以从某个字符再开始匹配的位置 } if(p[i]==p[j+1]) j++; //如果p[i]与p[j+1]正好匹配了，公共前后缀长度为j+1 ne[i]=j; //记录此时的j } //KMP匹配过程 for(int i=1,j=0;i<=m;i++){ //i从1开始，j从0开始；因每次都是要来比较s[i]与p[j+1]是否相等，所以错开一位 while(j&&s[i]!=p[j+1]){ //j没有退回起点而且当前s[i]和p[j+1]不匹配 j=ne[j]; //j退到可以从某个字符再开始匹配的位置 } if(s[i]==p[j+1]) j++; //如果s[i]和p[j+1]已经匹配，则开始比较下一个位置两字符串中字母是否相等 if(j==n){ //匹配成功 cout<<i-n<<" "; j=ne[j]; //若匹配成功，此时j已匹配过，下次匹配ne[j]位置和原串下一个位置 } } return 0; }
八、Trie树
在每个单词结尾结尾做标记，说明存在以该字母结尾的单词。
核心模板
int son[N][26],cnt[N],idx;
//idx代表点的编号，0号点既是根结点，又是空结点
//son数组存储树中每个结点的子结点（第一维表示结点编号，第二维表示26个孩子是否有，有则存储的是子节点编号，无则存储的是0；26个字母，最多26个子结点）
//cnt数组存储以每个结点结尾的单词数量
//插入一个字符串 void insert(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } //查询字符串出现的次数 int query(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cnt[p]; }
使用string写的模板
#include <iostream> #include <string> using namespace std; const int N=100010; int son[N][26],cnt[N],idx; void insert(string s){ int p=0; for(int i=0;i<s.size();i++){ int u=s[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int query(string s){ int p=0; for(int i=0;i<s.size();i++){ int u=s[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cnt[p]; } int main(){ int n; cin>>n; while(n--){ char op; cin>>op; string x; if(op=='I'){ cin>>x; insert(x); } else{ cin>>x; cout<<query(x)<<endl; } } return 0; }
题目链接：835. Trie字符串统计
8.1题目描述
维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N ，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗104
输入样例：
5 I abc Q abc Q ab I ab Q ab
输出样例：
1 0 1
8.2思路分析
直接套用模板即可，注意细节。
8.3代码实现
#include <iostream> using namespace std; const int N=100010; int son[N][26],cnt[N],idx; char str[N]; void insert(char str[]){ int p=0; //初始化p从0即根结点开始 for(int i=0;str[i];i++){ //遍历字符串str int u=str[i]-'a'; //将每个字母转换对应的0~25的下标 if(!son[p][u]) son[p][u]=++idx; //如果p所在结点没有以u所代表的字母，则将该字母作为p的子结点 p=son[p][u]; //p更新为其子节点 } cnt[p]++; //以p结尾的单词数量加1 } int query(char str[]){ int p=0; //初始化p从0即根结点开始 for(int i=0;str[i];i++){ //遍历字符串str int u=str[i]-'a'; //将每个字母转换对应的0~25的下标 if(!son[p][u]) return 0; //如果p所在结点没有以u所代表的字母，说明不存在以u所代表字母结尾的单词，直接返回0 p=son[p][u]; //p更新为其子节点 } return cnt[p]; //返回以p结尾的单词数量 } int main(){ int n; cin>>n; while(n--){ char op[2]; cin>>op>>str; if(op[0]=='I') insert(str); else cout<<query(str)<<endl; } return 0; }
