对于字符串 \(S\),若 \(S\) 的最小后缀为其本身,那么称 \(S\) 为 \(\text{Lyndon}\) 串(\(\text{Lyndon Word}\))
即
\[S \in L \Rightarrow \begin{cases} S是严格最小循环 \\ minsuf(s)=s \end{cases}
\]
\(Border(S)=\varnothing\)
如果 \(u,v \in L, u \prec v\Rightarrow uv \in L\)。
\(\mathcal{Proof.}\)
\(1) s=u'v,u\triangleleft u' \Rightarrow uv < u'v\)
\(2) \text{to prove uv<v}\)
\(2.1) u \triangleleft v \Rightarrow uv<v\)
\(2.2) u \sqsubseteq v \Rightarrow v=uv',v<v' \Leftrightarrow uv<uv' \Leftrightarrow uv<v\)
\(3) S=v',uv<v<v'\)
\(Q.E.D.\)
PS: \(\triangleleft\):严格小于,且不是前缀,必有一个字母不同,\(\sqsubseteq\):前缀
\(ex.\) 如果 \(u,v\in L,u<v \Rightarrow u^av^b\in L\)
显然。
任意字符串 \(s\) 可以分解为 \(s=s_1s_2s_3\dots s_k\),其中 \(s_i\) 是 \(\text{Lyndon}\) 串,\(s_i \ge s_{i+1}\),且这种分解方法是唯一的。
\(\mathcal{Proof.}\)
先证存在性:
初始时每段一个字符,然后不断地将相邻两段 \(s_i<s_{i+1}\) 合并。
再证唯一性:
若有两种方案,取第一次不同的位置,设 \(|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)\le s_{k+1}' \le s_i' < s_i,矛盾
\]
\(\mathcal{Proof.}\)
画图比划一下,容易(是真的)证得。
\(\text{Duval}\) 算法可以 \(O(n)\) 时间 \(O(1)\) 额外空间内求出 \(s[1\dots n]\) 的 \(\text{Lyndon}\) 分解。
即
\[CFL(s)=s_1 s_2 \dots s_k, s.t. \begin{cases} 1. s_i \in L \\ 2. s_1 \ge s_2 \ge \dots \ge s_k\end{cases}
\]
\(\mathcal{Lemma.}\)
若字符串 \(v\) 和字符 \(c\) 满足 \(vc\) 是某个 \(\text{Lyndon}\) 串的前缀,则对于字符 \(d>c\) 有 \(vd\) 是\(\text{Lyndon}\) 串。
也就是说,如果 \(uav \in L\),那么对于 \((uav)^kua'\):
如果 \(a<a'\),那么 \((uav)^kua' \in L\)
如果 \(a>a'\),那么 \(\forall w,(uav)^kua'w \notin L\)
\(\Rightarrow CFL[(uav)^kua'w]=(uav)^kCFL(ua'w)\)
因此,我们考虑下面这个算法过程:
用三个循环变量 \(i,j,k\) 维持一个循环不变式:
然后对于当前读入的字符 \(a\)
Code
int i, j, k;
for (i = 1; i <= N; ) {
for (k = i, j = k + 1; j <= N && s[j] >= s[k]; ++j) {
if (s[j] > s[k]) k = i;
else ++k;
}
while (i <= k) { lyndon[++cnt] = i + j - k - 1; i += j - k; }
}
先丢一个论文链接:The" Runs" Theorem
再说。
维护一个动态字符串 \(s[1\dots n]\),字符串的字符集是所有 \(|x|\le 10^9\) 的整数。要求支持两个操作:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章