Lyndon 分解
Lyndon 分解¶
首先我们介绍 Lyndon 分解的概念。
Lyndon 串:对于字符串 a
, b
, ab
, aab
, abb
, ababb
, abcd
都是 Lyndon 串。当且仅当
Lyndon 分解:串
Duval 算法¶
Duval 可以在
首先我们介绍另外一个概念:如果一个字符串
Duval 算法运用了贪心的思想。算法过程中我们把串
整体描述一下,该算法每一次尝试将
我们来更详细地解释一下算法的过程。定义一个指针
- 如果
s[j]=s[k] s[j] s_2 j,k - 如果
s[j]>s[k] s_2s[j] j k s_2 s_2 - 如果
s[j]<s[k] s_2s[j] s_2 j-k s_2 j,k
代码实现¶
下面的代码返回串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // duval_algorithm
vector<string> duval(string const& s) {
int n = s.size(), i = 0;
vector<string> factorization;
while (i < n) {
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k) {
factorization.push_back(s.substr(i, j - k));
i += j - k;
}
}
return factorization;
}
|
复杂度分析¶
接下来我们证明一下这个算法的复杂度。
外层的循环次数不超过
最小表示法(Finding the smallest cyclic shift)¶
对于长度为
我们构建串
于是我们在分解的过程中记录每一次的近似 Lyndon 串的开头即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | // smallest_cyclic_string
string min_cyclic_string(string s) {
s += s;
int n = s.size();
int i = 0, ans = 0;
while (i < n / 2) {
ans = i;
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k) i += j - k;
}
return s.substr(ans, n / 2);
}
|
习题¶
-
本页面主要译自博文 Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига 与其英文翻译版 Lyndon factorization 。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:sshwy, StudyingFather, orzAtalod
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用