Skip to content

Minimal String Representation

Definition

Minimum Representation is a method used to solve the string minimum representation problem.

Minimum Representation of a String

Cyclic Isomorphism

For a string \(S\), if there exists a position \(i\) such that

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

then \(S\) and \(T\) are said to be cyclically isomorphic.

Minimum Representation

The minimum representation of a string \(S\) is the lexicographically smallest string among all strings that are cyclically isomorphic to \(S\).

Naive Brute Force

We compare cyclic isomorphisms starting at \(i\) and \(j\) each time, recording the current comparison position as \(k\). Whenever a mismatch is encountered, we skip the larger one. The remaining index is the optimal solution.

Implementation

 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)

Explanation

This implementation performs well on random data, but special cases can be constructed to degrade its performance.

For example, for \(\texttt{aaa}\cdots\texttt{aab}\), it is not difficult to see that the algorithm's complexity degenerates to \(O(n^2)\).

We observe that the algorithm's efficiency decreases when the string contains multiple consecutive repeated substrings. We consider optimizing this process.

Minimum Representation Algorithm

Algorithm Core

Consider a pair of strings \(A, B\) with starting positions \(i, j\) in the original string \(S\), and suppose their first \(k\) characters are identical, i.e.,

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

Without loss of generality, assume \(S[i+k]>S[j+k]\). We find that no string starting at index \(l\) satisfying \(i\le l\le i+k\) can be the answer. Because for any string \(S_{i+p}\) (denoting the string starting at position \(i+p\), where \(p \in [0, k]\)), there always exists a string \(S_{j+p}\) that is lexicographically smaller.

Thus, during comparison, we can skip indices \(l \in [i, i+k]\) and directly compare \(S_{i+k+1}\).

In this way, we have optimized the naive brute-force approach.

Time Complexity

\(O(n)\)

Procedure

  1. Initialize pointers \(i = 0\), \(j = 1\); initialize match length \(k = 0\).
  2. Compare the characters at position \(k\). Based on the comparison result, update the corresponding pointer. If the pointers become equal after updating, arbitrarily increment one of them to ensure the two compared strings are different.
  3. Repeat the above process until the comparison ends.
  4. The answer is the smaller of \(i\) and \(j\).

Implementation

 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 协议之条款下提供，附加条款亦可能应用