跳转至

前綴函數與 KMP 算法

字符串前綴和後綴定義

關於字符串前綴、真前綴，後綴、真後綴的定義詳見 字符串基礎

前綴函數

定義

給定一個長度為 \(n\) 的字符串 \(s\)，其 前綴函數 被定義為一個長度為 \(n\) 的數組 \(\pi\)。 其中 \(\pi[i]\) 的定義是：

  1. 如果子串 \(s[0\dots i]\) 有一對相等的真前綴與真後綴：\(s[0\dots k-1]\) 和 \(s[i - (k - 1) \dots i]\)，那麼 \(\pi[i]\) 就是這個相等的真前綴（或者真後綴，因為它們相等））的長度，也就是 \(\pi[i]=k\)；
  2. 如果不止有一對相等的，那麼 \(\pi[i]\) 就是其中最長的那一對的長度；
  3. 如果沒有相等的，那麼 \(\pi[i]=0\)。

簡單來説 \(\pi[i]\) 就是，子串 \(s[0\dots i]\) 最長的相等的真前綴與真後綴的長度。

用數學語言描述如下：

\[ \pi[i] = \max_{k = 0 \dots i}\{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]\} \]

特別地，規定 \(\pi[0]=0\)。

過程

舉例來説，對於字符串 abcabcd，

\(\pi[0]=0\)，因為 a 沒有真前綴和真後綴，根據規定為 0

\(\pi[1]=0\)，因為 ab 無相等的真前綴和真後綴

\(\pi[2]=0\)，因為 abc 無相等的真前綴和真後綴

\(\pi[3]=1\)，因為 abca 只有一對相等的真前綴和真後綴：a，長度為 1

\(\pi[4]=2\)，因為 abcab 相等的真前綴和真後綴只有 ab，長度為 2

\(\pi[5]=3\)，因為 abcabc 相等的真前綴和真後綴只有 abc，長度為 3

\(\pi[6]=0\)，因為 abcabcd 無相等的真前綴和真後綴

同理可以計算字符串 aabaaab 的前綴函數為 \([0, 1, 0, 1, 2, 2, 3]\)。

計算前綴函數的樸素算法

過程

一個直接按照定義計算前綴函數的算法流程：

  • 在一個循環中以 \(i = 1\to n - 1\) 的順序計算前綴函數 \(\pi[i]\) 的值（\(\pi[0]\) 被賦值為 \(0\)）。
  • 為了計算當前的前綴函數值 \(\pi[i]\)，我們令變量 \(j\) 從最大的真前綴長度 \(i\) 開始嘗試。
  • 如果當前長度下真前綴和真後綴相等，則此時長度為 \(\pi[i]\)，否則令 j 自減 1，繼續匹配，直到 \(j=0\)。
  • 如果 \(j = 0\) 並且仍沒有任何一次匹配，則置 \(\pi[i] = 0\) 並移至下一個下標 \(i + 1\)。
實現

具體實現如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = i; j >= 0; j--)
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

1
2
3
4
5
6
7
8
9
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(i, -1, -1):
            if s[0 : j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

注：

  • string substr (size_t pos = 0, size_t len = npos) const;

顯見該算法的時間複雜度為 \(O(n^3)\)，具有很大的改進空間。

計算前綴函數的高效算法

第一個優化

第一個重要的觀察是 相鄰的前綴函數值至多增加 \(1\)。

參照下圖所示，只需如此考慮：當取一個儘可能大的 \(\pi[i+1]\) 時，必然要求新增的 \(s[i+1]\) 也與之對應的字符匹配，即 \(s[i+1]=s[\pi[i]]\), 此時 \(\pi[i+1] = \pi[i]+1\)。

\[ \underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i] = 3} ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i] = 3} ~ s_{i+1}}_{\pi[i+1] = 4} \]

所以當移動到下一個位置時，前綴函數的值要麼增加一，要麼維持不變，要麼減少。

實現

此時的改進的算法為：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = pi[i - 1] + 1; j >= 0; j--)  // improved: j=i => j=pi[i-1]+1
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

1
2
3
4
5
6
7
8
9
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(pi[i - 1] + 1, -1, -1):
            if s[0 : j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

在這個初步改進的算法中，在計算每個 \(\pi[i]\) 時，最好的情況是第一次字符串比較就完成了匹配，也就是説基礎的字符串比較次數是 n-1 次。

而由於存在 j = pi[i-1]+1（pi[0]=0）對於最大字符串比較次數的限制，可以看出每次只有在最好情況才會為字符串比較次數的上限積累 1，而每次超過一次的字符串比較消耗的是之後次數的增長空間。

由此我們可以得出字符串比較次數最多的一種情況：至少 1 次字符串比較次數的消耗和最多 n-2 次比較次數的積累，此時字符串比較次數為 n-1 + n-2 = 2n-3。

可見經過此次優化，計算前綴函數只需要進行 \(O(n)\) 次字符串比較，總複雜度降為了 \(O(n^2)\)。

第二個優化

在第一個優化中，我們討論了計算 \(\pi[i+1]\) 時的最好情況：\(s[i+1]=s[\pi[i]]\)，此時 \(\pi[i+1] = \pi[i]+1\)。現在讓我們沿着這個思路走得更遠一點：討論當 \(s[i+1] \neq s[\pi[i]]\) 時如何跳轉。

失配時，我們希望找到對於子串 \(s[0\dots i]\)，僅次於 \(\pi[i]\) 的第二長度 \(j\)，使得在位置 \(i\) 的前綴性質仍得以保持，也即 \(s[0 \dots j - 1] = s[i - j + 1 \dots i]\)：

\[ \overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1} \]

如果我們找到了這樣的長度 \(j\)，那麼僅需要再次比較 \(s[i + 1]\) 和 \(s[j]\)。如果它們相等，那麼就有 \(\pi[i + 1] = j + 1\)。否則，我們需要找到子串 \(s[0\dots i]\) 僅次於 \(j\) 的第二長度 \(j^{(2)}\)，使得前綴性質得以保持，如此反覆，直到 \(j = 0\)。如果 \(s[i + 1] \neq s[0]\)，則 \(\pi[i + 1] = 0\)。

觀察上圖可以發現，因為 \(s[0\dots \pi[i]-1] = s[i-\pi[i]+1\dots i]\)，所以對於 \(s[0\dots i]\) 的第二長度 \(j\)，有這樣的性質：

\[ s[0 \dots j - 1] = s[i - j + 1 \dots i]= s[\pi[i]-j\dots \pi[i]-1] \]

也就是説 \(j\) 等價於子串 \(s[\pi[i]-1]\) 的前綴函數值，即 \(j=\pi[\pi[i]-1]\)。同理，次於 \(j\) 的第二長度等價於 \(s[j-1]\) 的前綴函數值，\(j^{(2)}=\pi[j-1]\)

顯然我們可以得到一個關於 \(j\) 的狀態轉移方程：\(j^{(n)}=\pi[j^{(n-1)}-1], \ \ (j^{(n-1)}>0)\)

最終算法

所以最終我們可以構建一個不需要進行任何字符串比較，並且只進行 \(O(n)\) 次操作的算法。

而且該算法的實現出人意料的短且直觀：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

這是一個 在線 算法，即其當數據到達時處理它——舉例來説，你可以一個字符一個字符的讀取字符串，立即處理它們以計算出每個字符的前綴函數值。該算法仍然需要存儲字符串本身以及先前計算過的前綴函數值，但如果我們已經預先知道該字符串前綴函數的最大可能取值 \(M\)，那麼我們僅需要存儲該字符串的前 \(M + 1\) 個字符以及對應的前綴函數值。

應用

在字符串中查找子串：Knuth–Morris–Pratt 算法

該算法由 Knuth、Pratt 和 Morris 在 1977 年共同發佈[1]。

該任務是前綴函數的一個典型應用。

過程

給定一個文本 \(t\) 和一個字符串 \(s\)，我們嘗試找到並展示 \(s\) 在 \(t\) 中的所有出現（occurrence）。

為了簡便起見，我們用 \(n\) 表示字符串 \(s\) 的長度，用 \(m\) 表示文本 \(t\) 的長度。

我們構造一個字符串 \(s + \# + t\)，其中 \(\#\) 為一個既不出現在 \(s\) 中也不出現在 \(t\) 中的分隔符。接下來計算該字符串的前綴函數。現在考慮該前綴函數除去最開始 \(n + 1\) 個值（即屬於字符串 \(s\) 和分隔符的函數值）後其餘函數值的意義。根據定義，\(\pi[i]\) 為右端點在 \(i\) 且同時為一個前綴的最長真子串的長度，具體到我們的這種情況下，其值為與 \(s\) 的前綴相同且右端點位於 \(i\) 的最長子串的長度。由於分隔符的存在，該長度不可能超過 \(n\)。而如果等式 \(\pi[i] = n\) 成立，則意味着 \(s\) 完整出現在該位置（即其右端點位於位置 \(i\)）。注意該位置的下標是對字符串 \(s + \# + t\) 而言的。

因此如果在某一位置 \(i\) 有 \(\pi[i] = n\) 成立，則字符串 \(s\) 在字符串 \(t\) 的 \(i - (n - 1) - (n + 1) = i - 2n\) 處出現。

正如在前綴函數的計算中已經提到的那樣，如果我們知道前綴函數的值永遠不超過一特定值，那麼我們不需要存儲整個字符串以及整個前綴函數，而只需要二者開頭的一部分。在我們這種情況下這意味着只需要存儲字符串 \(s + \#\) 以及相應的前綴函數值即可。我們可以一次讀入字符串 \(t\) 的一個字符並計算當前位置的前綴函數值。

因此 Knuth–Morris–Pratt 算法（簡稱 KMP 算法）用 \(O(n + m)\) 的時間以及 \(O(n)\) 的內存解決了該問題。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
vector<int> find_occurrences(string text, string pattern) {
  string cur = pattern + '#' + text;
  int sz1 = text.size(), sz2 = pattern.size();
  vector<int> v;
  vector<int> lps = prefix_function(cur);
  for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
    if (lps[i] == sz2) v.push_back(i - 2 * sz2);
  }
  return v;
}

1
2
3
4
5
6
7
8
9
def find_occurrences(t, s):
    cur = s + '#' + t
    sz1, sz2 = len(t), len(s)
    ret = []
    lps = prefix_function(cur)
    for i in range(sz2 + 1, sz1 + sz2 + 1):
        if lps[i] == sz2:
            ret.append(i - 2 * sz2)
    return ret

字符串的週期

對字符串 \(s\) 和 \(0 < p \le |s|\)，若 \(s[i] = s[i+p]\) 對所有 \(i \in [0, |s| - p - 1]\) 成立，則稱 \(p\) 是 \(s\) 的週期。

對字符串 \(s\) 和 \(0 \le r < |s|\)，若 \(s\) 長度為 \(r\) 的前綴和長度為 \(r\) 的後綴相等，就稱 \(s\) 長度為 \(r\) 的前綴是 \(s\) 的 border。

由 \(s\) 有長度為 \(r\) 的 border 可以推導出 \(|s|-r\) 是 \(s\) 的週期。

根據前綴函數的定義，可以得到 \(s\) 所有的 border 長度，即 \(\pi[n-1],\pi[\pi[n-1]-1], \ldots\)。2

所以根據前綴函數可以在 \(O(n)\) 的時間內計算出 \(s\) 所有的週期。其中，由於 \(\pi[n-1]\) 是 \(s\) 最長 border 的長度，所以 \(n - \pi[n-1]\) 是 \(s\) 的最小週期。

統計每個前綴的出現次數

在該節我們將同時討論兩個問題。給定一個長度為 \(n\) 的字符串 \(s\)，在問題的第一個變種中我們希望統計每個前綴 \(s[0 \dots i]\) 在同一個字符串的出現次數，在問題的第二個變種中我們希望統計每個前綴 \(s[0 \dots i]\) 在另一個給定字符串 \(t\) 中的出現次數。

首先讓我們來解決第一個問題。考慮位置 \(i\) 的前綴函數值 \(\pi[i]\)。根據定義，其意味着字符串 \(s\) 一個長度為 \(\pi[i]\) 的前綴在位置 \(i\) 出現並以 \(i\) 為右端點，同時不存在一個更長的前綴滿足前述定義。與此同時，更短的前綴可能以該位置為右端點。容易看出，我們遇到了在計算前綴函數時已經回答過的問題：給定一個長度為 \(j\) 的前綴，同時其也是一個右端點位於 \(i\) 的後綴，下一個更小的前綴長度 \(k < j\) 是多少？該長度的前綴需同時也是一個右端點為 \(i\) 的後綴。因此以位置 \(i\) 為右端點，有長度為 \(\pi[i]\) 的前綴，有長度為 \(\pi[\pi[i] - 1]\) 的前綴，有長度為 \(\pi[\pi[\pi[i] - 1] - 1]\) 的前綴，等等，直到長度變為 \(0\)。故而我們可以通過下述方式計算答案。

實現 
1
2
3
4
vector<int> ans(n + 1);
for (int i = 0; i < n; i++) ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) ans[pi[i - 1]] += ans[i];
for (int i = 0; i <= n; i++) ans[i]++;

1
2
3
4
5
6
7
ans = [0] * (n + 1)
for i in range(0, n):
    ans[pi[i]] += 1
for i in range(n - 1, 0, -1):
    ans[pi[i - 1]] += ans[i]
for i in range(0, n + 1):
    ans[i] += 1

解釋

在上述代碼中我們首先統計每個前綴函數值在數組 \(\pi\) 中出現了多少次，然後再計算最後答案：如果我們知道長度為 \(i\) 的前綴出現了恰好 \(\text{ans}[i]\) 次，那麼該值必須被疊加至其最長的既是後綴也是前綴的子串的出現次數中。在最後，為了統計原始的前綴，我們對每個結果加 \(1\)。

現在考慮第二個問題。我們應用來自 Knuth–Morris–Pratt 的技巧：構造一個字符串 \(s + \# + t\) 並計算其前綴函數。與第一個問題唯一的不同之處在於，我們只關心與字符串 \(t\) 相關的前綴函數值，即 \(i \ge n + 1\) 的 \(\pi[i]\)。有了這些值之後，我們可以同樣應用在第一個問題中的算法來解決該問題。

一個字符串中本質不同子串的數目

給定一個長度為 \(n\) 的字符串 \(s\)，我們希望計算其本質不同子串的數目。

我們將迭代的解決該問題。換句話説，在知道了當前的本質不同子串的數目的情況下，我們要找出一種在 \(s\) 末尾添加一個字符後重新計算該數目的方法。

令 \(k\) 為當前 \(s\) 的本質不同子串數量。我們添加一個新的字符 \(c\) 至 \(s\)。顯然，會有一些新的子串以字符 \(c\) 結尾。我們希望對這些以該字符結尾且我們之前未曾遇到的子串計數。

構造字符串 \(t = s + c\) 並將其反轉得到字符串 \(t^{\sim}\)。現在我們的任務變為計算有多少 \(t^{\sim}\) 的前綴未在 \(t^{\sim}\) 的其餘任何地方出現。如果我們計算了 \(t^{\sim}\) 的前綴函數最大值 \(\pi_{\max}\)，那麼最長的出現在 \(s\) 中的前綴其長度為 \(\pi_{\max}\)。自然的，所有更短的前綴也出現了。

因此，當添加了一個新字符後新出現的子串數目為 \(|s| + 1 - \pi_{\max}\)。

所以對於每個添加的字符，我們可以在 \(O(n)\) 的時間內計算新子串的數目，故最終複雜度為 \(O(n^2)\)。

值得注意的是，我們也可以重新計算在頭部添加一個字符，或者從尾或者頭移除一個字符時的本質不同子串數目。

字符串壓縮

給定一個長度為 \(n\) 的字符串 \(s\)，我們希望找到其最短的「壓縮」表示，也即我們希望尋找一個最短的字符串 \(t\)，使得 \(s\) 可以被 \(t\) 的一份或多份拷貝的拼接表示。

顯然，我們只需要找到 \(t\) 的長度即可。知道了該長度，該問題的答案即為長度為該值的 \(s\) 的前綴。

讓我們計算 \(s\) 的前綴函數。通過使用該函數的最後一個值 \(\pi[n - 1]\)，我們定義值 \(k = n - \pi[n - 1]\)。我們將證明，如果 \(k\) 整除 \(n\)，那麼 \(k\) 就是答案，否則不存在一個有效的壓縮，故答案為 \(n\)。

假定 \(n\) 可被 \(k\) 整除。那麼字符串可被劃分為長度為 \(k\) 的若干塊。根據前綴函數的定義，該字符串長度為 \(n - k\) 的前綴等於其後綴。但是這意味着最後一個塊同倒數第二個塊相等，並且倒數第二個塊同倒數第三個塊相等，等等。作為其結果，所有塊都是相等的，因此我們可以將字符串 \(s\) 壓縮至長度 \(k\)。

證明

誠然，我們仍需證明該值為最優解。實際上，如果有一個比 \(k\) 更小的壓縮表示，那麼前綴函數的最後一個值 \(\pi[n - 1]\) 必定比 \(n - k\) 要大。因此 \(k\) 就是答案。

現在假設 \(n\) 不可以被 \(k\) 整除，我們將通過反證法證明這意味着答案為 \(n\)1。假設其最小壓縮表示 \(r\) 的長度為 \(p\)（\(p\) 整除 \(n\)），字符串 \(s\) 被劃分為 \(n / p \ge 2\) 塊。那麼前綴函數的最後一個值 \(\pi[n - 1]\) 必定大於 \(n - p\)（如果等於則 \(n\) 可被 \(k\) 整除），也即其所表示的後綴將部分的覆蓋第一個塊。現在考慮字符串的第二個塊。該塊有兩種解釋：第一種為 \(r_0 r_1 \dots r_{p - 1}\)，另一種為 \(r_{p - k} r_{p - k + 1} \dots r_{p - 1} r_0 r_1 \dots r_{p - k - 1}\)。由於兩種解釋對應同一個字符串，因此可得到 \(p\) 個方程組成的方程組，該方程組可簡寫為 \(r_{(i + k) \bmod p} = r_{i \bmod p}\)，其中 \(\cdot \bmod p\) 表示模 \(p\) 意義下的最小非負剩餘。

\[ \begin{gathered} \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 r_5}^p \\ r_0 ~ r_1 ~ r_2 ~ r_3 ~ \underbrace{\overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ r_0 ~ r_1}_{\pi[11] = 8} \end{gathered} \]

根據擴展歐幾里得算法我們可以得到一組 \(x\) 和 \(y\) 使得 \(xk + yp = \gcd(k, p)\)。通過與等式 \(pk - kp = 0\) 適當疊加我們可以得到一組 \(x' > 0\) 和 \(y' < 0\) 使得 \(x'k + y'p = \gcd(k, p)\)。這意味着通過不斷應用前述方程組中的方程我們可以得到新的方程組 \(r_{(i + \gcd(k, p)) \bmod p} = r_{i \bmod p}\)。

由於 \(\gcd(k, p)\) 整除 \(p\)，這意味着 \(\gcd(k, p)\) 是 \(r\) 的一個週期。又因為 \(\pi[n - 1] > n - p\)，故有 \(n - \pi[n - 1] = k < p\)，所以 \(\gcd(k, p)\) 是一個比 \(p\) 更小的 \(r\) 的週期。因此字符串 \(s\) 有一個長度為 \(\gcd(k, p) < p\) 的壓縮表示，同 \(p\) 的最小性矛盾。

綜上所述，不存在一個長度小於 \(k\) 的壓縮表示，因此答案為 \(k\)。

根據前綴函數構建一個自動機

讓我們重新回到通過一個分隔符將兩個字符串拼接的新字符串。對於字符串 \(s\) 和 \(t\) 我們計算 \(s + \# + t\) 的前綴函數。顯然，因為 \(\#\) 是一個分隔符，前綴函數值永遠不會超過 \(|s|\)。因此我們只需要存儲字符串 \(s + \#\) 和其對應的前綴函數值，之後就可以動態計算對於之後所有字符的前綴函數值：

\[ \underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need to store}} \]

實際上在這種情況下，知道 \(t\) 的下一個字符 \(c\) 以及之前位置的前綴函數值便足以計算下一個位置的前綴函數值，而不需要用到任何其它 \(t\) 的字符和對應的前綴函數值。

換句話説，我們可以構造一個 自動機（一個有限狀態機）：其狀態為當前的前綴函數值，而從一個狀態到另一個狀態的轉移則由下一個字符確定。

因此，即使沒有字符串 \(t\)，我們同樣可以應用構造轉移表的算法構造一個轉移表 \(( \text { old } \pi , c ) \rightarrow \text { new } _ { - } \pi\)：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void compute_automaton(string s, vector<vector<int>>& aut) {
  s += '#';
  int n = s.size();
  vector<int> pi = prefix_function(s);
  aut.assign(n, vector<int>(26));
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < 26; c++) {
      int j = i;
      while (j > 0 && 'a' + c != s[j]) j = pi[j - 1];
      if ('a' + c == s[j]) j++;
      aut[i][c] = j;
    }
  }
}

然而在這種形式下，對於小寫字母表，算法的時間複雜度為 \(O(|\Sigma|n^2)\)。注意到我們可以應用動態規劃來利用表中已計算過的部分。只要我們從值 \(j\) 變化到 \(\pi[j - 1]\)，那麼我們實際上在説轉移 \((j, c)\) 所到達的狀態同轉移 \((\pi[j - 1], c)\) 一樣，但該答案我們之前已經精確計算過了。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void compute_automaton(string s, vector<vector<int>>& aut) {
  s += '#';
  int n = s.size();
  vector<int> pi = prefix_function(s);
  aut.assign(n, vector<int>(26));
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < 26; c++) {
      if (i > 0 && 'a' + c != s[i])
        aut[i][c] = aut[pi[i - 1]][c];
      else
        aut[i][c] = i + ('a' + c == s[i]);
    }
  }
}

最終我們可在 \(O(|\Sigma|n)\) 的時間複雜度內構造該自動機。

該自動機在什麼時候有用呢？首先，記得大部分時候我們為了一個目的使用字符串 \(s + \# + t\) 的前綴函數：尋找字符串 \(s\) 在字符串 \(t\) 中的所有出現。

因此使用該自動機的最直接的好處是 加速計算字符串 \(s + \# + t\) 的前綴函數。

通過構建 \(s + \#\) 的自動機，我們不再需要存儲字符串 \(s\) 以及其對應的前綴函數值。所有轉移已經在表中計算過了。

但除此以外，還有第二個不那麼直接的應用。我們可以在字符串 \(t\) 是 某些通過一些規則構造的巨型字符串 時，使用該自動機加速計算。Gray 字符串，或者一個由一些短的輸入串的遞歸組合所構造的字符串都是這種例子。

出於完整性考慮，我們來解決這樣一個問題：給定一個數 \(k \le 10^5\)，以及一個長度 \(\le 10^5\) 的字符串 \(s\)，我們需要計算 \(s\) 在第 \(k\) 個 Gray 字符串中的出現次數。回想起 Gray 字符串以下述方式定義：

\[ \begin{aligned} g_1 &= \mathtt{a}\\ g_2 &= \mathtt{aba}\\ g_3 &= \mathtt{abacaba}\\ g_4 &= \mathtt{abacabadabacaba} \end{aligned} \]

由於其天文數字般的長度，在這種情況下即使構造字符串 \(t\) 都是不可能的：第 \(k\) 個 Gray 字符串有 \(2^k - 1\) 個字符。然而我們可以在僅僅知道開頭若干前綴函數值的情況下，有效計算該字符串末尾的前綴函數值。

除了自動機之外，我們同時需要計算值 \(G[i][j]\)：在從狀態 \(j\) 開始處理 \(g_i\) 後的自動機的狀態，以及值 \(K[i][j]\)：當從狀態 \(j\) 開始處理 \(g_i\) 後，\(s\) 在 \(g_i\) 中的出現次數。實際上 \(K[i][j]\) 為在執行操作時前綴函數取值為 \(|s|\) 的次數。易得問題的答案為 \(K[k][0]\)。

我們該如何計算這些值呢？首先根據定義，初始條件為 \(G[0][j] = j\) 以及 \(K[0][j] = 0\)。之後所有值可以通過先前的值以及使用自動機計算得到。為了對某個 \(i\) 計算相應值，回想起字符串 \(g_i\) 由 \(g_{i - 1}\)，字母表中第 \(i\) 個字符，以及 \(g_{i - 1}\) 三者拼接而成。因此自動機會途徑下列狀態：

\[ \begin{gathered} \text{mid} = \text{aut}[G[i - 1][j]][i] \\ G[i][j] = G[i - 1][\text{mid}] \end{gathered} \]

\(K[i][j]\) 的值同樣可被簡單計算。

\[ K[i][j] = K[i - 1][j] + [\text{mid} == |s|] + K[i - 1][\text{mid}] \]

其中 \([\cdot]\) 當其中表達式取值為真時值為 \(1\)，否則為 \(0\)。綜上，我們已經可以解決關於 Gray 字符串的問題，以及一大類與之類似的問題。舉例來説，應用同樣的方法可以解決下列問題：給定一個字符串 \(s\) 以及一些模式 \(t_i\)，其中每個模式以下列方式給出：該模式由普通字符組成，當中可能以 \(t_{k}^{\text{cnt}}\) 的形式遞歸插入先前的字符串，也即在該位置我們必須插入字符串 \(t_k\) \(\text{cnt}\) 次。以下是這些模式的一個例子：

\[ \begin{aligned} t_1 &= \mathtt{abdeca} \\ t_2 &= \mathtt{abc} + t_1^{30} + \mathtt{abd} \\ t_3 &= t_2^{50} + t_1^{100} \\ t_4 &= t_2^{10} + t_3^{100} \end{aligned} \]

遞歸代入會使字符串長度爆炸式增長，他們的長度甚至可以達到 \(100^{100}\) 的數量級。而我們必須找到字符串 \(s\) 在每個字符串中的出現次數。

該問題同樣可通過構造前綴函數的自動機解決。同之前一樣，我們利用先前計算過的結果對每個模式計算其轉移然後相應統計答案即可。

練習題目

參考資料與註釋

本頁面主要譯自博文 Префикс-функция. Алгоритм Кнута-Морриса-Пратта 與其英文翻譯版 Prefix function. Knuth–Morris–Pratt algorithm。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

  1. 在俄文版及英文版中該部分證明均疑似有誤。本文章中的該部分證明由作者自行添加。 ↩

  2. 金策 - 字符串算法選講 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, LeoJacob, Xeonacid, greyqz, StudyingFather, Marcythm, minghu6, Backl1ght
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用