跳转至

最小表示法

定義

最小表示法是用於解決字符串最小表示問題的方法。

字符串的最小表示

循環同構

當字符串 \(S\) 中可以選定一個位置 \(i\) 滿足

\[ S[i\cdots n]+S[1\cdots i-1]=T \]

則稱 \(S\) 與 \(T\) 循環同構

最小表示

字符串 \(S\) 的最小表示為與 \(S\) 循環同構的所有字符串中字典序最小的字符串

simple 的暴力

我們每次比較 \(i\) 和 \(j\) 開始的循環同構，把當前比較到的位置記作 \(k\)，每次遇到不一樣的字符時便把大的跳過，最後剩下的就是最優解。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
    ++k;
  } else {
    if (sec[(i + k) % n] > sec[(j + k) % n])
      ++i;
    else
      ++j;
    k = 0;
    if (i == j) i++;
  }
}
i = min(i, j);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
k, i, j = 0, 0, 1
while k < n and i < n and j < n:
    if sec[(i + k) % n] == sec[(j + k) % n]:
        k += 1
    else:
        if sec[(i + k) % n] > sec[(j + k) % n]:
            i += 1
        else:
            j += 1
        k = 0
        if i == j:
            i += 1
i = min(i, j)

解釋

該實現方法隨機數據下表現良好，但是可以構造特殊數據卡掉。

例如：對於 \(\texttt{aaa}\cdots\texttt{aab}\), 不難發現這個算法的複雜度退化為 \(O(n^2)\)。

我們發現，當字符串中出現多個連續重複子串時，此算法效率降低，我們考慮優化這個過程。

最小表示法

算法核心

考慮對於一對字符串 \(A,B\), 它們在原字符串 \(S\) 中的起始位置分別為 \(i,j\), 且它們的前 \(k\) 個字符均相同，即

\[ S[i \cdots i+k-1]=S[j \cdots j+k-1] \]

不妨先考慮 \(S[i+k]>S[j+k]\) 的情況，我們發現起始位置下標 \(l\) 滿足 \(i\le l\le i+k\) 的字符串均不能成為答案。因為對於任意一個字符串 \(S_{i+p}\)（表示以 \(i+p\) 為起始位置的字符串，\(p \in [0, k]\)）一定存在字符串 \(S_{j+p}\) 比它更優。

所以我們比較時可以跳過下標 \(l\in [i,i+k]\), 直接比較 \(S_{i+k+1}\)

這樣，我們就完成了對於上文暴力的優化。

時間複雜度

\(O(n)\)

過程

  1. 初始化指針 \(i\) 為 \(0\)，\(j\) 為 \(1\)；初始化匹配長度 \(k\) 為 \(0\)
  2. 比較第 \(k\) 位的大小，根據比較結果跳轉相應指針。若跳轉後兩個指針相同，則隨意選一個加一以保證比較的兩個字符串不同
  3. 重複上述過程，直到比較結束
  4. 答案為 \(i,j\) 中較小的一個

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
    k++;
  } else {
    sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
    if (i == j) i++;
    k = 0;
  }
}
i = min(i, j);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
k, i, j = 0, 0, 1
while k < n and i < n and j < n:
    if sec[(i + k) % n] == sec[(j + k) % n]:
        k += 1
    else:
        if sec[(i + k) % n] > sec[(j + k) % n]:
            i = i + k + 1
        else:
            j = j + k + 1
        if i == j:
            i += 1
        k = 0
i = min(i, j)
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用