最小表示法
libohan0905
·
·
个人记录
闲话
\color{black}{\text{D}}\color{red}\text{Y}：逊哥！最小表示法都不会？代码就几行！
蒟蒻的我：蒟蒻连 \color{black}{\text{KMP}} 都不会，代码短也。。。
\color{black}{\text{D}}\color{red}\text{Y}（摇手指嘲讽）：\color{black}{\text{Naive}}！
（这段话被 DY 删了三次，监视了五次）。
定义
循环同构
当字符串 S 中可以选定一个位置 i 满足：
S[i\cdots n]+S[1\cdots n-1]=T
则称 S 与 T 循环同构。
最小表示法
最小表示法就是找出字符串 S 的的循环同构串中字典序最小的一个。
P1368 【模板】最小表示法
求最小表示法中字典序最小的序列。
Solution
注意以下采用队长标号法从 0 开始的标号。
我们每次比较 i 和 j 开始的循环同构，把当前比较到的位置记作 k，每次遇到不一样的字符时便把大的删除，最后剩下的就是最优解。
int MinShow(){
int k=0,i=0,j=1;
while(k<n&&i<n&&j<n){
if(a[(i+k)%n]==a[(j+k)%n]) ++k;
else{
a[(i+k)%n]>a[(j+k)%n]?++i:++j;
k=0;
if(i==j) ++i;//保证i,j不相同
}
}
return min(i,j);
}
其实这个暴力在随机情况下表现良好，但会被精心构造的数据卡成 \mathcal{O}(n^2)，比如形如 aaa...ab 的串。
最小表示法
考虑对于一对字符串 A,B，它们在原字符串 S 中的起始位置分别为 i,j， 且它们的前 k 个字符均相同，即：
不妨先考虑 $S[i+k]>S[j+k]$ 的情况，我们发现起始位置下标 $l$ 满足 $i\le l\le i+k$ 的字符串均不能成为答案。
因为对于任意一个字符串 $S_{i+p}$（表示以 $i+p$ 为起始位置的字符串，$p \in [0, k]$，$i+p \in [i,i+k]$）一定存在字符串 $S_{j+p}$ 比它更优。
所以可以每次增加 $k+1$，具体实现看代码。
```cpp
int MinShow(){
int k=0,i=0,j=1;
while(k<n&&i<n&&j<n){
if(a[(i+k)%n]==a[(j+k)%n]) ++k;
else{
a[(i+k)%n]>a[(j+k)%n]?i+=k+1:j+=k+1;//优化
k=0;
if(i==j) ++i;
}
}
return min(i,j);
}
```
每次循环相当于自增 $i$ 或 $j$（增加 k 最后也是加到 $i$ 或 $j$ 上），这样就 $\mathcal{O}(n)$ 了。
### 应用
事实上应用不多。。。
- [AcWing 158. 项链](https://www.acwing.com/problem/content/160/)
本质上就是求两个串最小表示法是否相同。
- [HDU2609 How many](http://acm.hdu.edu.cn/showproblem.php?pid=2609)
几个本质不同的串，最小表示法加 `set` 判重即可。
### 参考资料
- [Oi-Wiki](https://oi-wiki.org/string/minimal-string/)