WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
字符串部分简介
字符串基础
标准库
字符串匹配
字符串哈希
字典树 (Trie)
前缀函数与 KMP 算法
Boyer-Moore算法
Z 函数(扩展 KMP)
自动机
AC 自动机
后缀数组 (SA)
后缀自动机 (SAM)
广义后缀自动机
后缀树
Manacher
回文树
序列自动机
最小表示法
Lyndon 分解
20 objects
本站非官方,所收集资源均来源于网络。
最小表示法 - 字符串
最小表示法是用于解决字符串最小表示问题的方法。 ## 字符串的最小表示 ### 循环同构 当字符串 $S$ 中可以选定一个位置 $i$ 满足 $$ S[i\cdots n]+S[1\cdots i-1]=T $$ 则称 $S$ 与 $T$ 循环同构 ### 最小表示 字符串 $S$ 的最小表示为与 $S$ 循环同构的所有字符串中字典序最小的字符串 ## simple 的暴力 我们每次比较 $i$ 和 $j$ 开始的循环同构,把当前比较到的位置记作 $k$ ,每次遇到不一样的字符时便把大的跳过,最后剩下的就是最优解。 ```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); ``` 随机数据下表现良好,但是可以构造特殊数据卡掉。 例如:对于 $\texttt{aaa}\cdots\texttt{aab}$ , 不难发现这个算法的复杂度退化为 $O(n^2)$ 。 我们发现,当字符串中出现多个连续重复子串时,此算法效率降低,我们考虑优化这个过程。 ## 最小表示法 ### 算法核心 考虑对于一对字符串 $A,B$ , 它们在原字符串 $S$ 中的起始位置分别为 $i,j$ , 且它们的前 $k$ 个字符均相同,即 $$ A[i \cdots i+k-1]=B[j \cdots j+k-1] $$ 不妨先考虑 $A[i+k]>B[j+k]$ 的情况,我们发现起始位置下标 $l$ 满足 $i\le l\le i+k$ 的字符串均不能成为答案。因为对于任意一个字符串 $S_{i+p}$ (表示以 $i+p$ 为起始位置的字符串)一定存在字符串 $S_{j+p}$ 比它更优。 所以我们比较时可以跳过下标 $l\in [i,i+k]$ , 直接比较 $S_{i+k+1}$ 这样,我们就完成了对于上文暴力的优化。 ### 时间复杂度 $O(n)$ ### 算法流程 1. 初始化指针 $i$ 为 $0$ , $j$ 为 $1$ ;初始化匹配长度 $k$ 为 $0$ 2. 比较第 $k$ 位的大小,根据比较结果跳转相应指针。若跳转后两个指针相同,则随意选一个加一以保证比较的两个字符串不同 3. 重复上述过程,直到比较结束 4. 答案为 $i,j$ 中较小的一个 ### 代码 ```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); ```