3u8833,蚊子有几颗牙齿,idpa会员
定义：对于字符串\(s\)，若\(s\)的最小后缀为其本身，那么称\(s\)为lyndon串
等价性：\(s\)为lyndon串等价于\(s\)本身是其循环移位中最小的一个
任意字符串\(s\)都可以分解为\(s = s_1 s_2 \dots s_k\)，其中\(\forall s_i\)为lyndon串且\(s_i \geqslant s_{i +1}\)。且这种分解方法是唯一的
引理1：若\(u, v\)为lyndon串，且\(u < v\)，那么\(uv\)为lyndon串
证明：
要证明\(uv\)为lyndon串只需证明\(uv\)本身为其最小后缀，
我们可以把所有的后缀分为两类，一类是由\(u\)的后缀加上\(v\)串的来，这部分的相对大小不会改变。
另一类是\(v\)串的后缀，因为\(v\)本身也是lyndon串，我们只需证明\(v > uv\)，因为\(v > u\)，显然成立
证明：
设\(pre(s, i)\)表示串\(s\)中\(s[1 \dots i]\)所代表的前缀
若有两种方案，取第一次不同的位置，设\(|s_i| > |s'_i|\)
令\(s_i = s'_i s'_{i + 1} \dots s'_{k} pre(s_{k + 1}, l)\)
反证法。根据定义，\(s_i < pre(s'_{k + 1}, l) \leqslant s'_{k + 1} \leqslant s'_i < s_i\)
矛盾
(下面内容抄袭并补充自参考资料2)
该算法可以在\(o(n)\)的时间内求出串\(s\)的lyndon分解
引理2：若字符串\(v\)和字符\(c\)满足\(vc\)是某个lyndon串的前缀，则对于字符\(d>c\)有\(vd\)是lyndon串
证明：和上面同样的思路，对于\(d\)之前的后缀相对大小不会改变，之后的后缀只会变大
该算法中我们仅需维护三个变量\(i, j, k\)
\(s[1..i - 1] = s_1 s_2 \dots s_g\)是固定下来的分解，也就是\(\forall l \in [1, g] s_l\)是lyndon串且\(s_l > s_{l + 1}\)
\(s[i .. k - 1] = t_1 t_2 \dots t_h v(h > 1)\) 是没有固定的分解，满足\(t_1\)是lyndon串，且\(t_1 = t_2 = \dots = t_h\)，\(v\)是\(t_h\)的(可为空的)真前缀，且有\(s_g > s[i .. k - 1]\)
当前读入的字符是\(s[k]\)，令\(j = k - |t_1|\)
分三种情况讨论
当\(s[k] = s[j]\)时，周期\(k - j\)继续保持
当\(s[k] > s[j]\)时，合并得到\(t_1 <- t_1 t_2 \dots t_h v s[k]\)是lyndon串
当\(s[k] < s[j]\)时，\(t_1, t_2, \dots, t_h\)的分解被固定下来，算法从\(v\)的开头处重新开始
我要评论#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 21) + 1;
char s[maxn];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1), j, k;
for(int i = 1; i <= n;) {
j = i; k = i + 1;
while(k <= n && s[j] <= s[k]) {
if(s[j] < s[k]) j = i;
else j++;
k++;
}
while(i <= j) {
printf("%d ", i + k - j - 1);
i += k - j;
}
}
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论