Tarjan
- 割点 (割顶)：删除这个点，极大连通分量数增加。
- 割边 (桥)：删除这个边， 极大连通分量数增加。
- 割边 \(\Leftrightarrow\) 不在任何一个回路。
差分约束
- 给定一个 \(n\) 元不等式组，每个不等式形如 \(x_i-x_j\leq c_k\)，判断是否有解。
等价变形为 \(x_i\leq x_j+c_k\)，与最短路的松弛条件很相似，所以可以从 \(j\) 向 \(i\) 建一条 \(c_k\) 的边，再新建 \(0\) 号点向所有点连边，边权为 \(0\)，从 \(0\) 号点开始跑单源最短路，如果有负环证明无解。
注：判负环应使用 Bellman-Ford 或 队列优化的 Bellman-Ford (某已死算法)。
欧拉图
- 欧拉回路：经过所有边，回到起点的一条路径。
- 奇点 / 偶点：度数为奇数 / 偶数的点。
欧拉图的判定
- 无向图：图连通，所有点都是偶点。
- 有向图：所有点都在一个强连通分量中，所有点出 / 入度相等。
Hierholzer 算法
-
求解欧拉回路。
-
条件：已经判断其存在欧拉回路。
-
选择任意顶点为起点，进行 DFS，并删掉所扩展的边，如果搜到一个点不能继续扩展，就把这个点放在最后面，这样就倒序模拟出了从起点开始的方案。
二分图
- 性质：没有奇环。
- 匹配：一个边的子集且所有点最多出现一次。
- 最大匹配：边数最大的匹配。
- 完美匹配：所有点都是匹配点的一个匹配。
二分图判定
- 黑白染色法。
二分图最大匹配
- 匈牙利算法。
原理：不断寻找增广路径，并通过递归实现 “撤销和更换” 操作。
霍尔定理
- 判断二分图是否存在完美匹配的充要条件。
- 条件：左部点个数 \(=\) 右部点个数。
对于任何左部点的子集 \(S\) 都要满足 \(\left|S\right|\leq\left|T\right|\)，其中 \(T\) 表示 \(S\) 中的点能到达右部点的并。
Hash
- 最好用的哈希表：
std::map
多项式 Hash
- 字符串 Hash 常用形式。
对于一个长度为 \(l\) 的字符串 \(s\) 而言，我们定义多项式 \(f_s=\sum_{i=1}^m s_i\times b^{l-i} \pmod P\) 为字符串 \(s\) 的 Hash 函数，实际上也可以将其理解为字符串 \(s\) 在 \(b\) 进制下的结果。
- 注：这里的 \(P\) 一般设为较大质数或
ull自然溢出，如果字符串长度过大可考虑使用双 Hash。
允许 \(k\) 次失配的字符串匹配
- 给定长度为 \(n\) 的源串 \(s\) 和长度为 \(m\) 的模式串 \(p\)，要求查找源串中有多少子串与模式串匹配。
- \(s‘\) 与 \(p\) 匹配，当且仅当 \(s‘\) 与 \(p\) 有 \(k\) 个位置字符不同。
- \(1\leq n,m\leq 10^6,0\leq k\leq 5\)
无法使用 KMP，但是可以 Hash + 二分。
枚举所有可能匹配的子串，假设现在枚举的子串为 \(s‘\)，通过 Hash + 二分可以快速找到 \(s‘\) 和 \(p\) 第一个不同的位置。之后将 \(s‘\) 和 \(p\) 在这个失配位置以及之前的部分删掉，继续查找下一个失配位置，这样的过程最多发生 \(k\) 次。
时间复杂度：\(O(m+kn\log m)\)
KMP
-
主要用来在源串中查找模式串的出现的次数和位置。
-
核心思想：减少不必要的匹配以加快匹配。
-
\(\rm nxt_i\) 表示以 \(i\) 为结尾的前缀中，最长相等前后缀的长度。
\(\rm nxt_i\) 求法：
for(int i=2,j=0;i<=m;i++){
while(j&&p[j+1]!=p[i])
j=nxt[j];
if(p[j+1]==p[i])
j++;
nxt[i]=j;
}
匹配做法：
for(int i=1,j=0;i<=n;i++){
while(j&&p[j+1]!=s[i])
j=nxt[j];
if(p[j+1]==s[i])
j++;
if(j==m){
ans[++cnt]=i-m+1;
j=nxt[j];
}
}
Trie 树
- 用边代表字母，从根到树上节点的一条路径代表一个字符串。
int next[N][26],cnt;
int num[N];
//插入
void insert(char *s,int l){
int p=0;
for(int i=0;i<l;i++){
int ch=s[i]-‘a‘;
if(!next[p][c]) next[p][c]=++cnt;
p=next[p][c];
}
num[p]++;
}
//查询
int find(char *s,int l){
int p=0;
for(int i=0;i<l;i++){
int ch=s[i]-‘a‘;
if(!next[p][c]) return 0;
p=next[p][c];
}
return num[p];
}
AC 自动机
-
可以进行多模式串匹配。
-
以 Trie 树的结构为基础，结合 KMP 的思想建立的。
建立 AC 自动机的步骤
- 基础的 Trie 结构：将所有模式串构成一棵 Trie。
- KMP 的思想：对 Trie 树上所有的节点构造 \(\rm Fail\) 指针。
\(\rm Fail\) 指针
- 指向所有模式串的前缀中匹配当前状态的最长后缀。
\(\rm Fail\) 求法：
void build(){
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}else tr[u][i]=tr[fail[u]][i];
}
}
}
多模式匹配：
int query(char *t){
int u=0,res=0;
for(int i=1;t[i];i++){
u=tr[u][t[i]-‘a‘];
for(int j=u;j&&e[j]!=-1;j=fail[j]){
res+=e[j];e[j]=-1;
}
}
return res;
}
时间复杂度：\(O(26n+m)\)，其中 \(n\) 为节点数，\(m\) 为源串长度。
Manacher
- 在长度为 \(n\) 的字符串 \(s\) 中找到所有回文串。