最小表示法
定义
最小表示法是用于解决字符串最小表示问题的方法．
字符串的最小表示
循环同构
当字符串 𝑆S
中可以选定一个位置 𝑖i 满足
𝑆[𝑖⋯𝑛]+𝑆[1⋯𝑖−1]=𝑇S[i⋯n]+S[1⋯i−1]=T
则称 𝑆S 与 𝑇T 循环同构
最小表示
字符串 𝑆S 的最小表示为与 𝑆S 循环同构的所有字符串中字典序最小的字符串
simple 的暴力
我们每次比较 𝑖i 和 𝑗j 开始的循环同构，把当前比较到的位置记作 𝑘k，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解．
实现
C++Python
---|---
---|---
解释
该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉．
例如：对于 𝚊𝚊𝚊⋯𝚊𝚊𝚋aaa⋯aab, 不难发现这个算法的复杂度退化为 𝑂(𝑛2)O(n2)．
我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程．
最小表示法
算法核心
考虑对于一对字符串 𝐴,𝐵A,B, 它们在原字符串 𝑆S 中的起始位置分别为 𝑖,𝑗i,j, 且它们的前 𝑘k 个字符均相同，即
𝑆[𝑖⋯𝑖+𝑘−1]=𝑆[𝑗⋯𝑗+𝑘−1]S[i⋯i+k−1]=S[j⋯j+k−1]
不妨先考虑 𝑆[𝑖 +𝑘] >𝑆[𝑗 +𝑘]S[i+k]>S[j+k] 的情况，我们发现起始位置下标 𝑙l 满足 𝑖 ≤𝑙 ≤𝑖 +𝑘i≤l≤i+k 的字符串均不能成为答案．因为对于任意一个字符串 𝑆𝑖+𝑝Si+p（表示以 𝑖 +𝑝i+p 为起始位置的字符串，𝑝 ∈[0,𝑘]p∈[0,k]）一定存在字符串 𝑆𝑗+𝑝Sj+p 比它更优．
所以我们比较时可以跳过下标 𝑙 ∈[𝑖,𝑖 +𝑘]l∈[i,i+k], 直接比较 𝑆𝑖+𝑘+1Si+k+1
这样，我们就完成了对于上文暴力的优化．
时间复杂度
𝑂(𝑛)O(n)
过程
- 初始化指针 𝑖i 为 00，𝑗j 为 11；初始化匹配长度 𝑘k 为 00
- 比较第 𝑘k 位的大小，根据比较结果跳转相应指针．若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
- 重复上述过程，直到比较结束
- 答案为 𝑖,𝑗i,j 中较小的一个
实现
C++Python
---|---
---|---
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, partychicken, StudyingFather, countercurrent-time, Early0v0, Enter-tainer, H-J-Granger, iamtwz, NachtgeistW, Suyun514, Xeonacid, AngelKitty, CCXXXI, cjsoft, diauweb, ezoixx130, fjzzq2002, GavinZhengOI, GekkaSaori, Gesrua, Junyan721113, karin0, Konano, ksyx, kxccc, LovelyBuggies, lychees, Makkiy, Menci, mgt, minghu6, P-Y-Y, Peanut-Tang, PotassiumWings, SamZhangQingChuan, shawlleyw, sshwy, SukkaW, Tiphereth-A, TrisolarisHD, weiyong1024 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用