2020-2021:teams:legal_string:jxm2001:字符串_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/02 18:10] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/04 11:28] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 310: | 行 310: | ||
| 如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。 | 如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。 | ||
| - | 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于其父节点的等价类中的最长串，于是当前串一定能与父节点最长串匹配。 | + | 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。 |
| - | 于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，匹配长度变为 $len_pos+1$。 | + | 于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。 |
| 每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。总时间复杂度 $O(n)$。 | 每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。总时间复杂度 $O(n)$。 | ||
| 行 541: | 行 541: | ||
| } | } | ||
| enter(ans); | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | === 习题五 === | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P3975|洛谷p3975]] | ||
| + | |||
| + | **题意** | ||
| + | |||
| + | 给定串 $S$，分别求其在不同位置相同子串只算一次和在不同位置相同子串算多次情况下的第 $k$ 小子串。 | ||
| + | |||
| + | **题解** | ||
| + | |||
| + | 先考虑不同位置相同子串算多次情况下的答案，首先易知每个子串出现次数为 $\text{endpos}$ 大小。 | ||
| + | |||
| + | 于是可以在 $\text{SAM}$ 上计算出每个结点包含子串数目，然后进行类似名次树的操作，即可得到第 $k$ 小子串。 | ||
| + | |||
| + | 对与不同位置相同子串只算一次情况下的答案，将 $\text{endpos}$ 大小强制修改为 $1$ 即可。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e6+5; | ||
| + | struct SAM{ | ||
| + | int ch[MAXN][26],fa[MAXN],len[MAXN],last,cnt; | ||
| + | int c[MAXN],topu[MAXN],sz[MAXN]; | ||
| + | LL sum[MAXN]; | ||
| + | void extend(int c){ | ||
| + | int p=last,np=++cnt; | ||
| + | last=np,len[np]=len[p]+1,sz[np]=1; | ||
| + | for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; | ||
| + | if(!p)fa[np]=1; | ||
| + | else{ | ||
| + | int q=ch[p][c]; | ||
| + | if(len[q]==len[p]+1)fa[np]=q; | ||
| + | else{ | ||
| + | int nq=++cnt;len[nq]=len[p]+1; | ||
| + | memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q]; | ||
| + | fa[q]=fa[np]=nq; | ||
| + | for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void init(char *s,int n){ | ||
| + | last=cnt=1; | ||
| + | mem(ch[1],0); | ||
| + | _for(i,0,n) | ||
| + | extend(s[i]-'a'); | ||
| + | } | ||
| + | void dfs(int pos,int k){ | ||
| + | if(k<=sz[pos])return; | ||
| + | k-=sz[pos]; | ||
| + | _for(i,0,26){ | ||
| + | if(!ch[pos][i])continue; | ||
| + | if(sum[ch[pos][i]]<k)k-=sum[ch[pos][i]]; | ||
| + | else{ | ||
| + | putchar('a'+i); | ||
| + | return dfs(ch[pos][i],k); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void query(int opt,int k){ | ||
| + | _rep(i,1,cnt)c[len[i]]++; | ||
| + | _rep(i,1,cnt)c[i]+=c[i-1]; | ||
| + | _rep(i,1,cnt)topu[c[len[i]]--]=i; | ||
| + | if(opt)for(int i=cnt;i>1;i--)sz[fa[topu[i]]]+=sz[topu[i]]; | ||
| + | else for(int i=cnt;i>1;i--)sz[i]=1; | ||
| + | sz[1]=0; | ||
| + | _rep(i,1,cnt)sum[i]=sz[i]; | ||
| + | for(int i=cnt;i;i--){ | ||
| + | _for(j,0,26) | ||
| + | sum[topu[i]]+=sum[ch[topu[i]][j]]; | ||
| + | } | ||
| + | if(sum[1]<k)puts("-1"); | ||
| + | else | ||
| + | dfs(1,k); | ||
| + | } | ||
| + | }solver; | ||
| + | char s[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%s",s); | ||
| + | solver.init(s,strlen(s)); | ||
| + | int t=read_int(),k=read_int(); | ||
| + | solver.query(t,k); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/字符串_4.1599041401.txt.gz · 最后更改: 2020/09/02 18:10 由 jxm2001
