高级数据结构
并查集
树状数组
线段树
可持久化数据结构
平衡树
AC自动机
KMP
朴素算法
char s[N],p[M];
for(int i=1;i<=n;i++)
{
bool flag = true;
for(int j=1;j<=m;j++)
if(s[i]!=p[j])
{
flag = false;
break;
}
}
优化版本O(n)
// 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;
}
// 匹配
//失配时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值
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];
// 匹配成功后的逻辑
}
}
Trie
优点:我们不难发现字典树中实际上记录了多个字符串的公共前缀,因此用于查询公共前缀时是十分高效的,他减少了无意义的字符串匹配,其查询效率要优于哈希树。
用来高效地存储和查找字符串
#include<iostream>
using namespace std;
const int N = 1e5+10;
// son存储trie树中的所有儿子节点,cnt表示以当前节点结尾的单词有多少个
// 下标是0的节点,即是根节点又是空节点
int son[N][26],cnt[N],idx;
char str[N];
void insert(char *str){
int p = 0; // 从根节点开始从前往后遍历
// 字符串结尾默认是'\0',因此可以用str[i]判断是否走到结尾
for(int i = 0;str[i];i++){
int u = str[i] - 'a'; // 将a~z转换成0~25
// 如果该位置不存在,则创建这个节点
// 为什么是++idx?用idx表示层数并赋值给p,拥有相同p的,具有相同的前缀
if(!son[p][u]) son[p][u] = ++idx;
// 走到下一个节点
p = son[p][u];
}
cnt[p] ++; // 表示以这个节点(p)为单词的数量多了一个,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 ;
cin >> n;
while(n--){
char op[2];
/*
为什么不用加&?
根据scanf函数的定义,其接收元素必须是类型与控制字符串元素对应的变量的地址。
&是取地址操作符,当接收元素不是地址时要用&获得变量的地址,当接收元素已经是地址时就不用&了,
而数组名就是地址。
*/
scanf("%s%s",op,str);
/*
*op是什么意思?
数组名就是首地址,*代表取这个首地址的值
*op 和 op[0] 具有大致相同的效果
*/
if(*op == 'I') insert(str);
else printf("%d\n",query(str));
}
return 0;
}
AC自动机是KMP和trie的结合体。KMP算法适用于单模式串的匹配,而AC自动机适合多模式串的匹配。例如:在一篇文章中我们找一句话可以用KMP,找多句话适用于AC自动机。并且可以这么认为,KMP是AC自动机的特殊情况。
算法流程
1. 根据给定模式串构建Trie树
2. 给Trie树中每一个结点构造fail指针(失配指针)使当前字符失配时跳转到具有最长公共前后缀的字符
继续匹配。如同 KMP算法一样, AC自动机在匹配时如果当前字符匹配失败,那么利用fail指针进行跳转。由此可知如果跳转,跳转后的串的前缀,必为跳转前的模式串的后缀并且跳转的新位置的深度(匹配字符个数)一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行 fail指针的求解。
3. 扫描文本串进行匹配。
参考文章:AC自动机
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10010,S=55,M=10000010;
int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],fail[N*S];
void insert()
{
int p = 0;
for(int i =0;str[i];i++)
{
int t = str[i]-'a';
if(!tr[p][t]) tr[p][t] = ++idx;//如果儿子不存在 创建一个新的节点
p = tr[p][t];
}
cnt[p] ++;
}
void build()
{
int hh=0,tt=-1;
for(int i=0;i<26;i++)//根节点以及第一层结点都是指向根节点,所以直接从第一层开始搜,也就是根的所有儿子开始搜
{
if(tr[0][i])
q[++tt] = tr[0][i];
}
while(hh<=tt)
{
int t = q[hh++];
for(int i=0;i<26;i++)
{
int p = tr[t][i];//p:自动机中某个第i层结点的idx -> KMP中的i
// if(p)
// {
// int j = fail[t];
// while(j && !tr[j][i]) j = fail[j];
// if(tr[j][i]) j = tr[j][i];
// fail[p] = j;
// q[++tt] = p;
// }
// 优化思路 在没有匹配时 把while循环多次跳 优化为 直接跳到fail指针最终跳到的位置
// 数学归纳法
// 假定在循环第i层时,前i-1层都求对了
// 在第i层没找到字母i,那么去第i-1层父结点t的failxt指针的位置就是它最终应该跳到的位置
if(!p) tr[t][i] = tr[fail[t]][i];//fail[t]:j 如果不存在儿子tr[t][i]的话
// 如果存在儿子节点 则对儿子节点的failxt指针赋值为tr[fail[t]][i]
else
{
fail[p] = tr[fail[t]][i];
q[++tt] = p;
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(fail, 0, sizeof fail);
idx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%s", str);
insert();
}
build();
scanf("%s", str);
int res = 0;
for (int i = 0, j = 0; str[i]; i ++ )
{
int t = str[i] - 'a';
j = tr[j][t];
int p = j;
while (p)
{
res += cnt[p];
cnt[p] = 0;
p = fail[p];
}
}
printf("%d\n", res);
}
return 0;
}
数学
质数
质数亦为素数,是指大于1的自然数中除了1和它本身以外不再有其他因数的自然数。与之相对的是合数。
判断方法
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
埃氏筛法
O(nloglogn)
const int N = 1e6+10;
int primes[N],cnt;
bool st[N];
//primes[]存放所有1~n的质数,cnt表示数量
//st表示是否被筛掉 1-》合数 0-》质数
void get_primes(int n)
{
int cnt=0;
for(int i = 2;i <= n;i ++ )
{
if(!st[i])
{
primes[cnt++]=i;
//没得到一个质数,筛掉其<=n的所有倍数。
//由于有些数会被重复的筛掉,故其时间复杂度到不到O(n)
for(int j = i*2;j <= n;j += i)
st[j]=true;
}
}
}
线性筛法
时间复杂度O(n)
const int N = 1e6+10;
int prime[N];
bool st[N];
//primes[] 记录1~n的所有的质数,cnt记录记录1~n的所有质数个数。
//st表示是否被筛掉 1-》合数 0-》质数
void get_primes(int n)
{
int cnt = 0;
for(int i = 2;i <= n;i ++ )
{
if(!st[i]) primes[cnt++]=i;
for(int j = 0;primes[j] <= n/i;j ++ )//注意
{
vis[primes[j]*i] = true;
if(i%primes[j]==0) break;
}
}
}
约数
若整数n除以整数d的余数为0,即d能整除n,则称d是n的约数,n是d的倍数,记为d|n。
正整数可以被唯一分解为N=pc11pc22pc33pc44pc55···pcnn.
其中pi都是质数,ci都是正整数,且pi<pj(i<j).
设每个正数N的约数个数f(N),
∑ni=1f(i)=n/1+n/2+···+n/n
N的正约数的个数为 (c1+1)(c2+1)···(cn+1)=∏mi=1(ci+1).
所有的正约数之和为(1+p1+p21+···+pc11)···(1+pm+p2m+pcnm)=∏mi=1(∑cij=0(pi)j)
试除法求所有约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}