最小表示法
定义
最小表示法是用于解决字符串最小表示问题的方法。
字符串的最小表示
循环同构
当字符串
则称
最小表示
字符串
simple 的暴力
我们每次比较
实现
=== "C++"
```cpp
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"
```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)
```解释
该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉。
例如：对于
我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。
最小表示法
算法核心
考虑对于一对字符串
不妨先考虑
所以我们比较时可以跳过下标
这样，我们就完成了对于上文暴力的优化。
时间复杂度
过程
- 初始化指针
- 比较第
- 重复上述过程，直到比较结束
- 答案为
实现
=== "C++"
```cpp
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"
```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)
```贡献者：@Menci@WenzelTian@Dejia@llh721113@mgt@Early@partychicken@Suyun514@fjzzq2002@karin0@TrisolarisHD@Xeonacid@Ir1d
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用