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