当前位置：首页 > news >正文

数据结构复习（单调栈，单调队列，KMP，manacher，tire，字符串哈希）

news 来源：原创 2025/9/8 11:15:33

单调栈：

介绍：

单调栈用于解决"寻找每个元素左侧/右侧第一个比它小/大的元素"类问题。栈中元素保持单调性，时间复杂度O(n)。
维护一个严格递增栈。对于每个元素a[i]，不断弹出栈顶比a[i]大的元素，剩下的栈顶即为第一个比它小的元素。栈中存储下标方便定位。

代码关键点：

while(getsize()&&a[top()]>=a[i]) pop()：维护栈的递增性

push(i)：存储下标而非值，方便后续比较

模版：

给定一个长度为 NN 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1−1。

输入格式

第一行包含整数 NN，表示数列长度。

第二行包含 NN 个整数，表示整数数列。

输出格式

共一行，包含 NN 个整数，其中第 ii 个数表示第 ii 个数的左边第一个比它小的数，如果不存在则输出 −1−1。

#include <bits/stdc++.h>

using namespace std;

const int N=100010;

int stk[N];

int tp=-1;

void push(int val){

stk[++tp]=val;

}

void pop(){

tp--;

}

int getsize(){

return tp+1;

}

int top(){

return stk[tp];

}

int main(){

int n;

scanf("%d",&n);

int p[N];

memset(p,-1,sizeof p);

int a[N];

for(int i=0;i<n;i++){

scanf("%d",&a[i]);

while(getsize()&&a[top()]>=a[i]){

pop();

}

if(getsize()){

p[i]=a[top()];

}

push(i);

}

for(int i=0;i<n;i++)cout<<p[i]<<' ';

}

单调队列：

介绍：

单调队列能在O(n)时间内处理滑动窗口极值问题。队列中元素保持单调性，队首即为当前窗口极值。

维护两个双端队列：一个递减（求最大值），一个递增（求最小值）

入队时从尾部移除破坏单调性的元素

检查队首元素是否超出窗口范围

代码关键点：

a[i]>a[q1.back()]：维护递减队列（最大值）

i-q1.front()+1>k：判断队首是否在窗口外

模版

给定一个大小为 n≤106n≤106 的数组。

有一个大小为 kk 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 kk 个数字。

每次滑动窗口向右移动一个位置。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

#include <bits/stdc++.h>

using namespace std;

const int N=1000010;

deque<int>q1,q2;

int n,k;

int a[N];

int ansm[N],ansM[N];

int main(){

scanf("%d%d",&n,&k);

for(int i=0;i<n;i++){

scanf("%d",&a[i]);

while(q1.size()&&a[i]>a[q1.back()]){

q1.pop_back();

}

while(q2.size()&&a[i]<a[q2.back()]){

q2.pop_back();

}

q1.push_back(i);

q2.push_back(i);

if(i-q1.front()+1>k)q1.pop_front();

if(i-q2.front()+1>k)q2.pop_front();

if(i+1>=k){

ansm[i]=q2.front();

ansM[i]=q1.front();

}

for(int i=k-1;i<n;i++)cout<<a[ansm[i]]<<' ';cout<<endl;

for(int i=k-1;i<n;i++)cout<<a[ansM[i]]<<' ';

}

字符串相关数据结构：

KMP:

介绍：

用于快速字符串匹配，核心是构建next数组（最长公共前后缀）。时间复杂度O(m+n)。

next数组构建：

j指向已匹配前缀末尾

当p[j+1] != p[i]时，j回退到next[j]

匹配成功时j前移

匹配过程：

主串指针i不回溯

利用next数组调整模式串指针j

模版

给定一个字符串 SS，以及一个模式串 PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 PP 在字符串 SS 中多次作为子串出现。

求出模式串 PP 在字符串 SS 中所有出现的位置的起始下标。

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int ne[N];

int pn,sn;

string p,s;

void build(){

memset(ne,-1,sizeof ne);

int j=-1;

for(int i=1;i<pn;i++){

while(j!=-1&&p[j+1]!=p[i])j=ne[j];

if(p[j+1]==p[i])j++;

ne[i]=j;

}

void slove(){

int j=-1;

for(int i=0;i<sn;i++){

while(j!=-1&&p[j+1]!=s[i]) j=ne[j];

if(p[j+1]==s[i])j++;

if(j==pn-1){

cout<<i-pn+1<<' ';

j=ne[j];

}

int main(){

cin>>pn>>p>>sn>>s;

build();

slove();

}

manacher:

介绍：

线性时间复杂度求最长回文子串。通过插入特殊字符统一处理奇偶长度回文。

关键步骤：

构建新字符串（如ab变为b变为#a#b#@）

维护当前最远右边界r及其中心l

利用对称性减少重复计算

d数组含义：
d[i]表示以i为中心的回文半径（包含特殊字符）。最终实际长度为d[i]-1。

模版；

题目描述

给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度。

字符串长度为 n。

输入格式

一行小写英文字符 a,b,c,⋯,y,z 组成的字符串 S。

输出格式

一个整数表示答案。

#include<bits/stdc++.h>using namespace std;const int N = 11000010;

string s;int a[N * 2];int len;int d[N * 2];int ans = 0;

// 构建包含特殊字符的新字符串void buildNewString() {

int n = s.size();

a[0] = '$'; // 添加起始特殊字符

for (int i = 0; i < n; ++i) {

a[2 * i + 1] = '#';

a[2 * i + 2] = s[i];

}

a[2 * n + 1] = '#';

a[2 * n + 2] = '@'; // 添加结束特殊字符

len = 2 * n + 2;}

void get() {

memset(d, 0, sizeof(d)); // 初始化 d 数组

int l = 0, r = 0;

for (int i = 1; i <= len; ++i) {

int k = (i > r)? 1 : min(d[l + r - i], r - i + 1);

while (i - k >= 0 && i + k <= len && a[i - k] == a[i + k]) k++;

d[i] = k--;

ans = max(ans, d[i]);

if (i + k > r) {

r = i + k;

l = i - k;

}

}}

int main() {

cin >> s;

if (s.empty()) { // 处理输入为空的情况

cout << 0 << endl;

return 0;

}

buildNewString();

get();

cout << ans - 1 << endl; // 最终结果需要减去添加的特殊字符数量

return 0;}

Trie树（字典树）

介绍：

高效存储/查询字符串集合的数据结构。每个节点对应一个字符，路径代表字符串。

操作实现：

插入：沿字符路径创建节点，末尾节点计数+1

查询：沿路径查找，返回末尾节点的计数

空间优化：

使用动态开点（tr[p][c]存储子节点编号）

数组大小根据题目数据范围设定

模版：

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 xx；

Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作，所有输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 NN，表示操作数。

接下来 NN 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。

每个结果占一行。

#include <bits/stdc++.h>

using namespace std;

const int N=20010;

int tr[N*20][30];

int zcnt[N*20];

int cnt=0;

int n;

void insert(string a){

int p=0;

for(char x:a){

if(tr[p][x-'a']==0)tr[p][x-'a']=++cnt;

p=tr[p][x-'a'];

}

zcnt[p]++;

}

int query(string a){

int p=0;

for(char x:a){

if(tr[p][x-'a']==0)return 0;

p=tr[p][x-'a'];

}

return zcnt[p];

}

int main(){

scanf("%d",&n);

for(int i=0;i<n;i++){

char op;

cin>>op;

if('I'==op){

string tmp;

cin>>tmp;

insert(tmp);

}else {

string tmp;

cin>>tmp;

cout<<query(tmp)<<endl;

}

字符串哈希

介绍：

通过预处理前缀哈希，实现O(1)时间比较任意子串。常用质数基数+自然溢出模。

实现要点：

pre[i] = pre[i-1]*p + s[i]：计算前缀哈希

power[i]存储p^i，用于快速计算子串哈希

比较时使用pre[r] - pre[l-1]*power[r-l+1]

注意事项：

选择合适质数（如131, 13331）降低冲突概率

无符号类型自然溢出实现自动取模

模版：

给定一个长度为 nn 的字符串，再给定 mm 个询问，每个询问包含四个整数 l1,r1,l2,r2l1,r1,l2,r2，请你判断 [l1,r1][l1,r1] 和 [l2,r2][l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 nn 和 mm，表示字符串长度和询问次数。

第二行包含一个长度为 nn 的字符串，字符串中只包含大小写英文字母和数字。

接下来 mm 行，每行包含四个整数 l1,r1,l2,r2l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 11 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

#include <bits/stdc++.h>

typedef unsigned long long ull;

using namespace std;

const int N=100010;

ull p=131;

ull pre[N];

ull power[N];

int n,m;

string s;

ull get(int l,int r){

return pre[r]-pre[l-1]*power[r-l+1];

}

int main(){

scanf("%d%d",&n,&m);

cin>>s;

power[0]=1;

int len=s.size();

for(int i=0;i<len;i++){

pre[i+1]=pre[i]*p+(s[i]);

power[i+1]=power[i]*p;

}

for(int i=0;i<m;i++){

int l,r,a,b;

scanf("%d%d%d%d",&l,&r,&a,&b);

if(get(l,r)==get(a,b)){

cout<<"Yes";

}else cout<<"No";

cout<<endl;

}

单调栈：

介绍：

模版：

单调队列：

介绍：

模版

KMP:

介绍：

模版

manacher:

介绍：

模版；

Trie树（字典树）

介绍：

模版：

字符串哈希

介绍：

模版：

相关文章：