7.17 Graph&String

\[\begin{aligned}\begin{gathered}\\huge\mathcal{G}\texttt{raph&}\mathcal{S}\texttt{tring}

\quad{\large\texttt{-Zhang_RQ}}

\end{gathered}\end{aligned}

\]

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\) 中找到所有回文串。