最小表示法

循环同构

对于字符串 \(S,\ S.length = n,\\ \forall \ i, \ S[i..n] + S[0..i-1]\) 与 \(S\) 循环同构。

最小表示

字符串 \(S\) 的循环同构中字典序最小的字符串

function minimumRepresentation(s: string): number {
  let len: number = 0, i: number = 0, j: number = 1
  const n: number = s.length
  while (len < n && i < n && j < n) {
    const a: string = s[(i + len) % n]
    const b: string = s[(j + len) % n]
    if (a == b) {
      ++len
    } else {
      if (a > b) {
        ++i
      }
      else {
        ++j
      }
      len = 0
      if (i == j) {
        ++i
      }
    }
  }
  return Math.min(i, j)
}

算法时间复杂度最好情况 \(O(n)\)，最坏 \(O(n^2)\)
对于形如 \(s = yyy...yyx,\ s.length = n\) 的数据，复杂度为 \(O(n^2)\)。

优化

对于长为 \(n\) 的字符串 \(S\) 的两个循环同构 \(S_i,\ S_j\ (i < j)\), 易知 \(S_i,\ S_j\) 是 \(2S = S + S\) 的子字符串。假设它们的前 \(l\ (l < n)\) 个字符相同，即 \(S[i..i+l-1] = S[j..j+l-1]\)

如果它们的下一个字符 \(S[i+l] \not= S[j + l]\)，不妨设 \(S[i+l] < S[j+l]\) 时，那么对 \(\forall k \in [0, l]\)，\(S_{i+k} < S_{j+k}\)

证明
\(S_{i+k} = S[i..i+l-1] + S[i+l] + S[i+l+1...]\)
\(S_{j+k} = S[j..j+l-1] + S[j+l] + S[j+l+1...]\)
\(\because S[i..i+l-1] = S[j..j+l-1],\ S[i+l] < S[j+l]\)
\(\therefore S_{i+k} < S_{j+k}\)

\(S[i+l] > S[j+l]\) 的情况类似。
所以 \(j\) 可以跳过下标 \([j, j+l]\)，直接去比较 \(S[i] 和 S[j+l+1]\)

function minimumRepresentation(s: string): number {
  let len: number = 0, i: number = 0, j: number = 1
  const n: number = s.length
  while (len < n && i < n && j < n) {
    const a: string = s[(i + len) % n]
    const b: string = s[(j + len) % n]
    if (a == b) {
      ++len
    } else {
      if (a > b) {
        i = i + len + 1
      }
      else {
        j = j + len + 1
      }
      len = 0
      if (i == j) {
        ++i
      }
    }
  }
  return Math.min(i, j)
}

此时时间复杂度稳定在 \(O(n)\)。