lyndon word
定义:对于字符串(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)
矛盾
duval算法
(下面内容抄袭并补充自参考资料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; }
参考资料
lyndon word
金策—字符串选讲
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605709.html