文档章节

Lyndon分解和最小循环表示学习

o
 osc_zoa3moe9
发布于 2019/12/07 18:32
字数 1067
阅读 13
收藏 0

精选30+云产品,助力企业轻松上云!>>>

做CF594E涉及的两个知识点。以下字符串采用Python记法。

Lyndon分解

定义 $S$ 是Lyndon串,当且仅当对于任意有意义的正整数 $i$ 有 $S<S[i:]$.

定义 $S$ 的Lyndon分解是一个Lyndon串的序列 $s_1, s_2, \ldots, s_n$, 使得 $S=s_1s_2 \cdots s_n$ 并且 $s_1 \ge s_2 \ge \cdots \ge s_n$.

Lyndon分解存在且唯一。

不难发现,Lyndon分解可以这么得到:对于 $S$, 取最小的后缀 $S[i:]$, $S$ 的Lyndon分解,是在 $S[:i]$ 的Lyndon分解的最后加上一项 $S[i:]$ 得到的序列。

于是,Lyndon分解可以用后缀数组求,但是这样太复杂了。

Lyndon分解的Duval算法:

设原字符串为 $S$. 逐个加入字符,设已能确定 $S[:i]$ 的Lyndon分解 $s_1, s_2, \ldots, s_n$ 为 $S$ 的Lyndon分解的前缀,再尽可能地扩充字符串 $S[i:k]$, 使得 $S[i:k]$ 具有Lyndon周期 $t$, 也就是说,$S[i:k]=(m \times t)u$, 其中 $m$ 是正整数,$t$ 是Lyndon串,$u$ 是 $t$ 的(可以为空的)真前缀。考虑加入字符 $S[k]$, 若 $k=|S|$ 则令 $S[k]=-\infty$.

  • 若 $S[k]<S[k-|t|]$, 则 $S[i:k+1]$ 就没有Lyndon周期了。不过此时 $S[:i+m|t|]$ 的Lyndon分解已确定,即在 $S[:i]$ 的Lyndon分解末尾添加 $m$ 个 $t$, 取新参数 $i \gets i+n|t|$ 重来。
  • 若 $S[k]=S[k-|t|]$, 则 $t$ 也是 $S[i:k+1]$ 的Lyndon周期。
  • 若 $S[k]>S[k-|t|]$, 则 $S[i:k+1]$ 的Lyndon周期是其本身。

实现上我们只需要维护 $i, k$ 以及 $j=k-|t|$. 代码链接

扩充 $S[i:k]$ 的过程中 $i+k\le2|S|$ 且随扩充总轮数递增,因此该算法时间 $O(|S|)$, 除去输入输出只需要 $O(1)$ 额外空间,是一个非常简短而高效的算法。

最小循环表示

最小循环表示,也就是对于字符串 $S$, 求出最小的 $T_i=S[i:]S[:i]$.

我们维护两个决策 $i, j$, 满足 $i<j$ 并且 $[0, i)$ 和 $(i, j)$ 中的整数都不是最优决策。

初始时,设 $i=0, j=1$.

我们通过枚举比较求出 $T_i$ 和 $T_j$ 的最长公共前缀 $k$.

  • 若 $T_i=T_j$, $T_i$ 即为最优解。这是因为 $S$ 以 $j-i$ 为循环节循环,而 $(i, j)$ 中任何整数都不是最优决策。
  • 若 $T_i<T_j$, 说明 $[j, j+k]$ 内的整数不是最优决策,因为它总比 $[i, i+k]$ 内的对应决策劣,因此令 $j \gets j+k+1$. 上述性质未改变。
  • 若 $T_i>T_j$, 同理令 $i \gets i+k+1$, 若此后 $i \ge j$ 则再令 $j \gets i+1$, 上述性质仍未改变。

当 $j \ge |S|$ 时,我们发现 $[0, i)$ 和 $(i, |S|)$ 中的整数都不可能为最小决策了,所以 $T_i$ 是唯一的最优解;否则重复此过程。

$i+j+k \le 3|S|$ 随枚举总次数递增,因此该算法时间 $O(|S|)$, 除去输入输出只需要 $O(1)$ 额外空间,是一个非常简短而高效的算法。

代码:$n$($n \le 3\times10^5$)项整数序列的最小循环表示。

不过这份代码由于在OJ上刷常数榜,不仅加入了输入输出优化,还破环为链以节省取模的时间,空间略大。

 1 #include <bits/stdc++.h>
 2 char r[1<<25], *rc=r, w[1<<25], *wc=w;
 3 int rd() {
 4     int a;
 5     bool b;
 6     unsigned char c;
 7     while(c=*rc++-48, c>9&c!=253);
 8     b=(c==253);
 9     for(a=b?0:c; (c=*rc++-48)<10; a=a*10+c);
10     return b?-a:a;
11 }
12 void wr(int v) {
13     char s[10], *p=s;
14     while(*p++=v%10+48, v/=10);
15     while(*wc++=*--p, p!=s);
16 }
17 const int N=3e5;
18 int n, x[2*N];
19 int main() {
20     int i, j, k;
21     fread(r, 1, 1<<25, stdin);
22     n=rd();
23     for(i=0; i<n; ++i) x[i]=rd();
24     memcpy(x+n, x, n*sizeof(int));
25     for(i=0, j=1, k=0; j<n&&k<n; ) {
26         int xi=x[i+k], xj=x[j+k];
27         if(xi==xj) ++k;
28         else if(xi<xj) j+=k+1, k=0;
29         else {
30             i+=k+1, k=0;
31             if(i>=j) j=i+1;
32         }
33     }
34     for(k=0; k<n; ++k) wr(x[i+k]), *wc++=' ';
35     wc[-1]='\n';
36     fwrite(w, 1, wc-w, stdout);
37     return 0;
38 }
最小循环表示
o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
[CF594E]Cutting the Line

$newcommand{qed}{square}$字符串神题。 要点:Lyndon分解,扩展KMP, 最小循环表示,贪心。 题目链接 题意 已知字符串 $S$, 请你把它切成不超过 $k$ 段,并翻转其中若干段,使得最终字符串的...

osc_zoa3moe9
2019/12/07
6
0
LOJ129 Lyndon 分解

Lyndon 分解 样例 样例输入 1ababa样例输出 12 4 5 样例输入 2bbababaabaaabaaaab样例输出 21 2 4 6 9 13 18 样例输入 3azAZ0129样例输出 32 4 8 数据范围与提示 $1le |s| le 2^{20}$ OZY的题...

osc_gjsta20x
2019/07/11
4
0
字符串算法选讲

符号与约定 周期和border 对于一个 对于一个 周期与 一个简明的小结论 对于拥有周期 然后可以做的就是对于一个位置 用 Weak Periodicity Lemma 对于一个字符串 钦定 若 否则 然后我们就发现了...

Rose_max
04/01
0
0
GDOI2020 游记

Day -6 真的啥都不想说。 感觉就是颓了一年,啥都没学。 知识点,点分家族、字符串、网络流一无所知。更别说技巧和套路了。 代码能力也下降了好多。 今年是真的药丸。 Day -4 开始停课。 第一...

osc_5rgbamh9
06/21
5
0
GDOI2020 游记

Day -6 真的啥都不想说。 感觉就是颓了一年,啥都没学。 知识点,点分家族、字符串、网络流一无所知。更别说技巧和套路了。 代码能力也下降了好多。 今年是真的药丸。 Day -4 开始停课。 第一...

ATS_nantf
06/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Xcode中的版本与版本 - Version vs build in Xcode

问题: I have an app that I developed with Xcode 3 and recently started editing with Xcode 4. In the target summary I have the iOS application target form with fields: identifie......

javail
30分钟前
7
0
如何在Python中将字典键作为列表返回? - How to return dictionary keys as a list in Python?

问题: In Python 2.7 , I could get dictionary keys , values , or items as a list: 在Python 2.7中 ,我可以将字典键 , 值或项作为列表获取: >>> newdict = {1:0, 2:0, 3:0}>>> newd......

技术盛宴
今天
17
0
2020世界人工智能大会开幕首日 百度与浦发银行达成战略合作

本文作者:y****n 7月9日,2020世界人工智能大会开幕首日,百度与浦发银行签署战略合作协议,将在人工智能、金融科技等多个领域进一步深化合作。双方将优势互补,实现人工智能技术在金融领域...

百度开发者中心
昨天
26
0
Java中C ++ Pair 的等价物是什么? - What is the equivalent of the C++ Pair in Java?

问题: Is there a good reason why there is no Pair<L,R> in Java? 有没有一个很好的理由说明Java中没有Pair<L,R> ? What would be the equivalent of this C++ construct? 这个C ++构造的......

富含淀粉
今天
18
0
中国饭店协会数据表明

记者了解到,中国饭店协会数据表明,2018年全国餐饮收入42716亿元,同比增长9.5%.根据国家统计局数据显示,截至2017年底,限额以上餐饮行业的从业人数达到2232万人,巨大的餐饮市场背后,餐饮行业的...

asd369
今天
35
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部