最小表示法

最小表示法是用于解决字符串最小表示问题的方法。

字符串的最小表示

循环同构

当字符串 中可以选定一个位置 满足

则称 与 循环同构

最小表示

字符串 的最小表示为与 循环同构的所有字符串中字典序最小的字符串

simple 的暴力

我们每次比较 和 开始的循环同构，把当前比较到的位置记作 ，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// C++ Version
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
14
# Python Version
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)

随机数据下表现良好，但是可以构造特殊数据卡掉。

例如：对于 , 不难发现这个算法的复杂度退化为 。

我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。

最小表示法

算法核心

考虑对于一对字符串 , 它们在原字符串 中的起始位置分别为 , 且它们的前 个字符均相同，即

不妨先考虑 的情况，我们发现起始位置下标 满足 的字符串均不能成为答案。因为对于任意一个字符串 （表示以 为起始位置的字符串，）一定存在字符串 比它更优。

所以我们比较时可以跳过下标 , 直接比较

这样，我们就完成了对于上文暴力的优化。

时间复杂度

算法流程

  1. 初始化指针 为 ， 为 ；初始化匹配长度 为
  2. 比较第 位的大小，根据比较结果跳转相应指针。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
  3. 重复上述过程，直到比较结束
  4. 答案为 中较小的一个

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// C++ Version
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
14
# Python Version
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)
build本页面最近更新：2022/4/19 15:12:01，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：countercurrent-time, Early0v0, Enter-tainer, fjzzq2002, iamtwz, Ir1d, karin0, ksyx, llh721113, partychicken, SukkaW, Suyun514, TrisolarisHD, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论