2020-2021:teams:i_dont_know_png:potassium:lyndon
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:i_dont_know_png:potassium:lyndon [2020/05/19 15:50] potassium 创建 |
2020-2021:teams:i_dont_know_png:potassium:lyndon [2020/05/22 20:12] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| 又由于单个字符是一个 Lyndon 串，可依靠这种思想进行合并。 | 又由于单个字符是一个 Lyndon 串，可依靠这种思想进行合并。 | ||
| - | Lyndon 分解：将字符串 $s$ 分成 $s=s_1s_2s_3..s_m$，使得每个 $s_i$ 都是 Lyndon 串，且 $\forall 1\le i<n:s_i\ge s_{i+1}$。 | + | Lyndon 分解：将字符串 $s$ 分成 $s=s_1s_2s_3\ldots s_m$，使得每个 $s_i$ 都是 Lyndon 串，且 $\forall 1\le i<n:s_i\ge s_{i+1}$。 |
| ===== 算法 ===== | ===== 算法 ===== | ||
| 行 19: | 行 19: | ||
| Duval 算法过程： | Duval 算法过程： | ||
| - | 维护三个变量 $i,j,k$ ， $[0..i-1]$ 为一些已经确定的 Lyndon 串， $[i..k-1]$ 为 Lyndon 串 $t$ 进行多次重复后加一个 $t$ 的真前缀 $v$。当前处理的字符位置为 $k$ ， $j=k-len(t)$。分类讨论： | + | 维护三个变量 $i,j,k$ ， $[0\ldots i-1]$ 为一些已经确定的 Lyndon 串， $[i\ldots k-1]$ 为 Lyndon 串 $t$ 进行多次重复后加一个 $t$ 的真前缀 $v$。当前处理的字符位置为 $k$ ， $j=k-len(t)$。分类讨论： |
| * $s[k]=s[j]$ 。直接 $k=k+1,j=j+1$。 | * $s[k]=s[j]$ 。直接 $k=k+1,j=j+1$。 | ||
| - | * $s[k] > s[j]$。此时 $s[i..k]$ 为 Lyndon 串，合并一下， $k=k+1,j=i$ 。 | + | * $s[k] > s[j]$。此时 $s[i\ldots k]$ 为 Lyndon 串，合并一下， $k=k+1,j=i$ 。 |
| * $s[k]<s[j]$ 。此时每一个 $t$ 都为 Lyndon 串，将 $i$ 前移到 $v$ 的开头。 | * $s[k]<s[j]$ 。此时每一个 $t$ 都为 Lyndon 串，将 $i$ 前移到 $v$ 的开头。 | ||
| 行 76: | 行 76: | ||
| * 题解：对于每次询问 $(l,k)$ ，首先算出 $r=nxt[l]$ ，进行分类讨论： | * 题解：对于每次询问 $(l,k)$ ，首先算出 $r=nxt[l]$ ，进行分类讨论： | ||
| * $lcp(suf(l),suf(r))=0$ ：答案必为 $[l,r-1]$ 。 | * $lcp(suf(l),suf(r))=0$ ：答案必为 $[l,r-1]$ 。 | ||
| - | * $lcp(suf(l),suf(r))>0$ ，设 $len = r-l,tot=len\cdot\left\lfloor\dfrac{lcp+len}{len}\right\rfloor$ ，即 $s[l..r-1]$ 重复出现的长度。 | + | * $lcp(suf(l),suf(r))>0$ ，设 $len = r-l,tot=len\cdot\left\lfloor\dfrac{lcp+len}{len}\right\rfloor$ ，即 $s[l\cdots r-1]$ 重复出现的长度。 |
| * $tot\bmod k=0$ ：设 $remain=n-(l+tot\cdot len)$ - $remain=0$ ：此时可均分，答案为 $[l,l+\left\lfloor\dfrac {tot}{k}\right\rfloor-1]$ - $remain \ne0$ ：此时将最后一段连接到结尾，答案为 $[l+tot-\left\lfloor\dfrac{tot}{k}\right\rfloor,n]$ | * $tot\bmod k=0$ ：设 $remain=n-(l+tot\cdot len)$ - $remain=0$ ：此时可均分，答案为 $[l,l+\left\lfloor\dfrac {tot}{k}\right\rfloor-1]$ - $remain \ne0$ ：此时将最后一段连接到结尾，答案为 $[l+tot-\left\lfloor\dfrac{tot}{k}\right\rfloor,n]$ | ||
| * $tot\bmod k\ne 0$ ：此时 $remain$ 段比循环段小，故答案为从 $l$ 开始的一段 $[l,l+len\cdot\left\lfloor\dfrac{tot/len}{k}\right\rfloor-1]$ | * $tot\bmod k\ne 0$ ：此时 $remain$ 段比循环段小，故答案为从 $l$ 开始的一段 $[l,l+len\cdot\left\lfloor\dfrac{tot/len}{k}\right\rfloor-1]$ | ||
2020-2021/teams/i_dont_know_png/potassium/lyndon.1589874646.txt.gz · 最后更改: 2020/05/19 15:50 由 potassium
