浦口网站建设,产品推广方案,建e网室内设计网怎么用,网页设计心得体会报告怎么写摘抄自quack的ppt。
这部分和 s a sa sa的关联比较大#xff0c;可以加深对 s a sa sa的理解。
Part 1
如果字符串 s s s的字典序在 s s s以及 s s s的所有后缀中是最小的#xff0c;则称 s s s是一个 lyndon \text{lyndon} lyndon串。 lyndon \text{lyndon} lyndon分解可以加深对 s a sa sa的理解。
Part 1
如果字符串 s s s的字典序在 s s s以及 s s s的所有后缀中是最小的则称 s s s是一个 lyndon \text{lyndon} lyndon串。 lyndon \text{lyndon} lyndon分解指的是把一个字符串分成若干段每一段都是一个 lyndon \text{lyndon} lyndon串问最少的分割段数。
方法一用后缀数组 s a [ 1 ] sa[1] sa[1]就是 lyndon \text{lyndon} lyndon分解的最后那一段 lyndon \text{lyndon} lyndon分解倒数第二段就是把 s a [ 1 ] sa[1] sa[1]那一段排除之后排的最靠前的 s a sa sa以此类推。 s a sa sa可以用来 lyndon \text{lyndon} lyndon分解依赖于以下结论
定义数组 a [ i ] a[i] a[i]为最小的 j j j使得 j i ji ji且 S [ j : ∣ S ∣ − 1 ] S [ i : ∣ S ∣ − 1 ] S[j:|S|-1]S[i:|S|-1] S[j:∣S∣−1]S[i:∣S∣−1]如果不存在这样的 j j j可以认为 a i ∣ S ∣ a_i|S| ai∣S∣。
那么 S S S的 lyndon \text{lyndon} lyndon分解的第一项为 S [ 0 : a [ 0 ] − 1 ] S[0:a[0]-1] S[0:a[0]−1]且后面 m − 1 m-1 m−1项就是 S [ a [ 0 ] : ∣ S ∣ − 1 ] S[a[0]:|S|-1] S[a[0]:∣S∣−1]的 lyndon \text{lyndon} lyndon分解。
证明显然此时不能划分到 a [ 0 ] a[0] a[0]之后否则可以根据原串后缀的信息道出矛盾。因此只需论证划分到 a [ 0 ] a[0] a[0]合法即可。注意到此时 S [ a [ 0 ] ] ≤ S [ 0 ] S[a[0]]\le S[0] S[a[0]]≤S[0]因此对于任意 j ∈ [ 1 , a [ 0 ] − 1 ] j\in [1,a[0]-1] j∈[1,a[0]−1]一定满足 S [ 0 : a [ 0 ] − j − 1 ] ≠ S [ j : a [ 0 ] − 1 ] S[0:a[0]-j-1]\ne S[j:a[0]-1] S[0:a[0]−j−1]S[j:a[0]−1]又因为 s a [ 0 ] s a [ j ] sa[0]sa[j] sa[0]sa[j]因此 S [ 0 : a [ 0 ] − 1 ] S[0:a[0]-1] S[0:a[0]−1]一定是它的所有后缀当中最小的。
基本性质 1.1 1.1 1.1 若字符串 u , v u,v u,v是 lyndon \text{lyndon} lyndon串且 u v uv uv则 u v uv uv是 lyndon \text{lyndon} lyndon串。 1.2 1.2 1.2 若字符串 s s s是 lyndon \text{lyndon} lyndon串 s ′ a sa s′a是 s s s的前缀那么 s ′ b ( b a ) sb(ba) s′b(ba)是 lyndon \text{lyndon} lyndon串。注意 s ′ a sa s′a不一定是 lyndon \text{lyndon} lyndon串
方法二duval 算法
每次维护一个前缀的 lyndon \text{lyndon} lyndon分解。这个前缀 S [ 1 : k − 1 ] S[1:k-1] S[1:k−1]可以被分解成 s 1 , . . . , s g s_1,...,s_g s1,...,sg这些 lyndon \text{lyndon} lyndon串和 S [ i : k − 1 ] S[i:k-1] S[i:k−1]这个近似 lyndon \text{lyndon} lyndon串形如 w k w ′ w^kw wkw′ w w w是一个 lyndon \text{lyndon} lyndon串 w ′ w w′是 w w w的前缀。
具体的三个变量 i , j , k i,j,k i,j,k维持一个循环不变式 S [ 0 : i − 1 ] s 1 s 2 . . . s g S[0:i-1]s_1s_2...s_g S[0:i−1]s1s2...sg 是已经固定下来的分解满足 s l s_l sl是 lyndon \text{lyndon} lyndon串且 s l ≥ s l 1 s_l\ge s_{l1} sl≥sl1否则可以合并。 S [ i : k − 1 ] t 1 t 2 . . . t h v S[i:k-1]t_1t_2...t_hv S[i:k−1]t1t2...thv是没有固定的分解满足 t 1 t_1 t1是 lyndon \text{lyndon} lyndon串 t 1 t 2 . . . t h t_1t_2...t_h t1t2...th v v v是 t h t_h th的可为空的真前缀令 j k − ∣ t 1 ∣ jk-|t_1| jk−∣t1∣。 复杂度为 O ( n ) O(n) O(n)。比sa快啊
代码
Part 2 lyndon \text{lyndon} lyndon分解的应用 1.3 1.3 1.3 给定长为 n n n的字符串 S S S求出 S S S的最小表示法。
方法将 S S SS SS lyndon \text{lyndon} lyndon分解找到分解后最后一个字符串它的首字符为 S S [ p ] SS[p] SS[p]且 p ∈ [ 0 , ∣ S ∣ ) p\in [0,|S|) p∈[0,∣S∣)。可以证明 S S [ p : p ∣ S ∣ − 1 ] SS[p:p|S|-1] SS[p:p∣S∣−1]是字典序最小的。运用第一条引理转化为比较在原串中的后缀即sa 1.4 1.4 1.4 给定长度为 n n n的字符串 S S S将 S S S分为最多 k k k个串 c 1 c 2 . . . c k c_1c_2...c_k c1c2...ck求 max c i \max c_i maxci的最小值。
方法看到字典序容易想到 lyndon \text{lyndon} lyndon分解。首先把 S S S lyndon \text{lyndon} lyndon分解成 s 1 , . . . , s g s_1,...,s_g s1,...,sg如果 k ≥ g k\ge g k≥g那么答案即为 s 1 s_1 s1否则如果 s 1 s 2 s_1s_2 s1s2那么显然可以分成 s 1 s_1 s1和剩下的所有串答案还是 s 1 s_1 s1。因此考虑分解成 s 1 m s g s_1^ms_g s1msg的情况如果 k m km km那么答案还是 s 1 s_1 s1如果 k ≤ m k\le m k≤m那么尽量均分一下即可。
推广多次询问每次询问 S S S的一段后缀的答案。
考虑求出原串的sa数组显然可以求出第一项以及重复次数可以用哈希这样就做完了。 1.5 1.5 1.5 求 S S S的每个前缀的字典序最小的后缀
首先把 S S S lyndon \text{lyndon} lyndon分解成 s 1 , . . . , s g s_1,...,s_g s1,...,sg显然 s 1 . . . s k s_1...s_k s1...sk的字典序最小的后缀是 s k s_k sk。但是前缀取到分解出来的 lyndon \text{lyndon} lyndon串半截时答案可能不一样。
考虑 duval \text{duval} duval算法求 lyndon \text{lyndon} lyndon分解的过程分类讨论
若 s [ k ] s [ j ] s[k]s[j] s[k]s[j]此时 a n s [ k ] ans[k] ans[k]应该等于 i i i因为 s [ i : k ] s[i:k] s[i:k]构成一个新的 lyndon \text{lyndon} lyndon串若 s [ k ] s [ j ] s[k]s[j] s[k]s[j]此时 a n s [ k ] a n s [ j ] k − j ans[k]ans[j]k-j ans[k]ans[j]k−j若 s [ k ] s [ j ] s[k]s[j] s[k]s[j]在 lyndon \text{lyndon} lyndon串开头时更新 1.6 1.6 1.6 求 S S S的每个前缀的字典序最大的后缀
首先把字符比较反过来然后要尽量向左取当 s [ k ] ≤ s [ j ] s[k]\le s[j] s[k]≤s[j]的时候 s [ i : k ] s[i:k] s[i:k]这一段都保持了是一个近似 lyndon \text{lyndon} lyndon串所以都取近似 lyndon \text{lyndon} lyndon串的左端点 i i i作为答案即可。
ps感觉这个算法就只能考论文题。。。太恶心了。。。
