2020-2021:teams:wangzai_milk:后缀自动机
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:后缀自动机 [2020/05/16 00:03] infinity37 [它怎么写] |
2020-2021:teams:wangzai_milk:后缀自动机 [2020/05/16 00:10] (当前版本) infinity37 |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 可以发现后缀树的每个节点对应一个后缀集合，每个点对应的后缀集合是这个点的字数中所有结束节点所表示的后缀的集合。我们可以发现有一个性质，对于只有一个儿子的费结束节点，他的后缀集合与他儿子的后缀集合相同，后缀自动机上只需要考虑所有后缀集合不同的节点，所以我们可以发现有意义的点只有结束节点和有一个以上儿子的节点。所以我们把所有非上述两种的点压缩到下面最近的一个上述两种点，我们就可以得到这个后缀自动机。 | 可以发现后缀树的每个节点对应一个后缀集合，每个点对应的后缀集合是这个点的字数中所有结束节点所表示的后缀的集合。我们可以发现有一个性质，对于只有一个儿子的费结束节点，他的后缀集合与他儿子的后缀集合相同，后缀自动机上只需要考虑所有后缀集合不同的节点，所以我们可以发现有意义的点只有结束节点和有一个以上儿子的节点。所以我们把所有非上述两种的点压缩到下面最近的一个上述两种点，我们就可以得到这个后缀自动机。 | ||
| + | |||
| + | ===== 一个构造模版 ===== | ||
| + | <code c++> | ||
| + | struct SAM | ||
| + | { | ||
| + | int trs[N<<1][26],fa[N<<1],len[N<<1]; | ||
| + | int cnt,last; | ||
| + | void init(){cnt=last=1;} | ||
| + | void insert(int x) | ||
| + | { | ||
| + | int p = last,np=++cnt,q,nq; | ||
| + | last = np,len[np]=len[p]+1; | ||
| + | end[np] = true; | ||
| + | for(;p&&!trs[p][x];p=fa[p])trs[p][x] = np; | ||
| + | if(!p)fa[np] = 1; | ||
| + | else | ||
| + | { | ||
| + | q = trs[p][x]; | ||
| + | if(len[q]==len[p]+1)fa[np]=q; | ||
| + | else | ||
| + | { | ||
| + | fa[nq=++cnt]=fa[q]; | ||
| + | len[nq]=len[p]+1; | ||
| + | memcpy(trs[nq],trs[q],sizeof(trs[q])); | ||
| + | fa[np] = fa[q] = nq; | ||
| + | for(;p&&trs[p][x]==q;p=fa[p])trs[p][x]=nq; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | }sam; | ||
| + | </code> | ||
| ===== 好题推荐 ====== | ===== 好题推荐 ====== | ||
| ===== 广义后缀自动机 ===== | ===== 广义后缀自动机 ===== | ||
2020-2021/teams/wangzai_milk/后缀自动机.1589558585.txt.gz · 最后更改: 2020/05/16 00:03 由 infinity37
