Lyndon 分解
Lyndon 分解¶
首先我们介绍 Lyndon 分解的概念。
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
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用