Minimal Representation

Definition

The minimal representation method is used to solve minimal-representation problems for strings.

Minimal Representation of a String

Cyclic Equivalence

If a position $i$ is selected in string $S$ such that

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

then $S$ and $T$ are called cyclically equivalent.

Minimal Representation

The minimal representation of string $S$ is the lexicographically smallest string among all strings cyclically equivalent to $S$.

Simple Brute Force

We compare the cyclic equivalents beginning at $i$ and $j$ each time, denote the position currently being compared by $k$, skip the larger one whenever different characters are encountered, and the one remaining at the end is the optimal answer.

Implementation

C++

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);

Python

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 data can be constructed to defeat it.

For example, for $\mathtt{aaa}\cdots\mathtt{aab}$, it is not difficult to see that the complexity of this algorithm deteriorates to $O(n^2)$.

When many consecutive repeated substrings occur in the string, this algorithm becomes less efficient, so we consider optimizing this process.

Minimal Representation Method

Core of the Algorithm

Consider a pair of strings $A,B$ whose starting positions in the original string $S$ are $i,j$, respectively, and whose first $k$ characters are identical, that is,

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

First consider the case $S[i+k]>S[j+k]$. We find that no string whose starting-position index $l$ satisfies $i\le l\le i+k$ can be the answer. For every string $S_{i+p}$ (denoting the string starting at $i+p$, where $p \in [0, k]$), there is always a string $S_{j+p}$ better than it.

Therefore, when comparing, we can skip the indices $l\in [i,i+k]$ and directly compare $S_{i+k+1}$.

Thus, we have completed the optimization of the brute force method above.

Time complexity

$O(n)$

Process

1. Initialize pointer $i$ to $0$ and $j$ to $1$; initialize the matching length $k$ to $0$.
2. Compare the $k$-th characters and jump this pointer according to the comparison result. If the two pointers become equal after the jump, increment either one to ensure that the two strings being compared are different.
3. Repeat the above process until the comparison ends.
4. The answer is the smaller of $i,j$.

Implementation

C++

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);

Python

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)