【算法】kmp、Trie、并查集、堆
文章目录
- 1.kmp
- 2.Trie
- 3.并查集
- 4.堆
1.kmp
KMP 的精髓就是 next 数组：也就是用 next[j] = k;简单理解就是：来保存子串某个位置匹配失败后，回退的位置。
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106输入样例：
3 aba 5 ababa输出样例：
0 2
#include <iostream>
using namespace std;
const int N = 100010,M = 1000010;
int n,m;
int ne[N];
char p[N],s[M];
int main()
{
cin>>n>>p+1>>m>>s+1;
//ne数组
for(int i =2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j= ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
//KMP匹配
for(int i = 1,j=0;i<=m;i++)
{
while(j&&s[i]!=p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j==n)
{
printf("%d ",i-n);
//匹配成功之后要回退
j = ne[j];
}
}
return 0;
}
2.Trie
Trie树是高效快速存储和查找字符串集合的数据结构。我们直接通过一幅图来了解即可：
Trie树中有个二维数组 son[N][26]，只包含小写字母，cnt数组表示当前这个点结尾的单词有多少个。下标是0的点既是根节点又是空节点
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 xx；Q x询问一个字符串在集合中出现了多少次。共有 N 个操作，所有输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为
I x或Q x中的一种。输出格式
对于每个询问指令
Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。每个结果占一行。
数据范围
1≤N≤2∗1041≤N≤2∗104
输入样例：
5 I abc Q abc Q ab I ab Q ab输出样例：
1 0 1
#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;
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];
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I') insert(str);
else printf("%d\n",query(str));
}
return 0;
}
3.并查集
快速处理问题：1.将两个集合合并2.询问两个元素是否在一个集合当中
基本原理：用树的形式维护集合，每个集合的编号是根结点的编号，每个结点都存储父节点是谁，p[x]表示x的父节点，所以可以快速找到每个点属于哪个集合。问题1：如何去判断树根：if(p[x]==x)
问题2：如何求x的集合编号：while(p[x]!=x) x = p[x]
问题3：合并两个集合：px是x的集合编号，py是y的集合编号，p[x]=y即可
优化问题2：路径压缩：在找根结点的路径上，所有在路径上的结点都指向根结点。可以基本看成O（1）复杂度
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
M a b或Q a b中的一种。输出格式
对于每个询问指令
Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出Yes，否则输出No。每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4输出样例：
Yes No Yes
#include <iostream>
using namespace std;
int n,m;
const int N = 100010;
int p[N];
int find(int x)
{
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i =1;i<=n;i++) p[i] = i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
题目稍微变形一下：
给定一个包含 n 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，aa 和 bb 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
C a b，Q1 a b或Q2 a中的一种。输出格式
对于每个询问指令
Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出Yes，否则输出No。对于每个询问指令
Q2 a，输出一个整数表示点 aa 所在连通块中点的数量每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5输出样例：
Yes 2 3
#include <iostream>
using namespace std;
int n,m;
const int N = 100010;
int p[N],sz[N];
int find(int x)
{
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++)
{
p[i] = i;
sz[i] = 1;
}
while(m--)
{
char op[5];
int a,b;
scanf("%s",op);
if(op[0] == 'C')
{
scanf("%d%d",&a,&b);
if(find(a) == find(b)) continue;
sz[find(b)] += sz[find(a)];
p[find(a)] = find(b);
}
else if(op[1] == '1')
{
scanf("%d%d",&a,&b);
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
else
{
scanf("%d",&a);
printf("%d\n",sz[find(a)]);
}
}
return 0;
}
4.堆
分为大根堆和小根堆。小根堆是每个点都小于等于左右孩子，根结点就是最小的。根为x,则x的左孩子：2x，右孩子：2x+1。核心操作是down和up，向下和向上调整。对于小根堆，down的逻辑：如果某个值变大了，往下移。up的逻辑：某个值变小了，往上移。
堆排序
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 mm 小的数。
数据范围
1≤m≤n≤1051≤m≤n≤105，
1≤数列中元素≤1091≤数列中元素≤109输入样例：
5 3 4 5 1 3 2输出样例：
1 2 3
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int heap[N],sz;
void down(int u)
{
int t = u;
if(u*2<=sz&&heap[u*2]<heap[t]) t = u*2;
if(u*2+1<=sz&&heap[u*2+1]<heap[t]) t = u*2+1;
if(u!=t)
{
swap(heap[u],heap[t]);
down(t);
}
}
void up(int u)
{
while(u/2&&heap[u/2]>heap[u])
{
swap(heap[u/2],heap[u]);
u/=2;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%d",&heap[i]);
sz=n;
for(int i = n/2;i;i--) down(i);
while(m--)
{
printf("%d ",heap[1]);
heap[1] = heap[sz];
sz--;
down(1);
}
return 0;
}
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k 个插入的数；C k x，修改第 k 个插入的数，将其变为 x；现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为
I x，PM，DM，D k或C k x中的一种。输出格式
对于每个输出指令
PM，输出一个结果，表示当前集合中的最小值。每个结果占一行。
数据范围
1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109
数据保证合法。输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM输出样例：
-10 6
删除第k个插入的数：需要多开两个数组存储第k个数是什么
#include <iostream>
#include <string.h>
using namespace std;
const int N = 100010;
int h[N],ph[N],hp[N],sz;
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u)
{
int t = u;
if(u*2<=sz&&h[u*2]<h[t]) t = u*2;
if(u*2+1<=sz&&h[u*2+1]<h[t]) t = u*2+1;
if(u!=t)
{
heap_swap(u,t);
down(t);
}
}
void up(int u)
{
while(u/2&&h[u/2]>h[u])
{
heap_swap(u/2,u);
u/=2;
}
}
int main()
{
int n,m=0;
scanf("%d",&n);
while(n--)
{
char op[10];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I"))
{
scanf("%d",&x);
sz++;
m++;
ph[m] = sz,hp[sz] = m;
h[sz] = x;
up(sz);
}
else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
else if(!strcmp(op,"DM"))
{
heap_swap(1,sz);
sz--;
down(1);
}
else if(!strcmp(op,"D"))
{
scanf("%d",&k);
k = ph[k];
heap_swap(k,sz);
sz--;
down(k),up(k);
}
else
{
scanf("%d%d",&k,&x);
k=ph[k];
h[k] = x;
down(k);
up(k);
}
}
return 0;
}