UOJ#35 后缀排序 SAM做法

大家好我是oscar..这可能是我第一次发博客诶.. 由于我比较弱，所以可能讲了一些大家都会的东西...求不D... 好了不说太多，先步入正题... 今天我们的挑战是：不建后缀数组完成任务（网上的做法好像都是建出后缀数组再用后缀数组的性质算出height数组） 假装大家都会后缀自动机啦（我这种蒟蒻花了约一个星期才搞懂） 首先将 从last到root用suffix link连接的路径上的节点 标上结束标记（ ```cpp inline void update() { node *p=last; while(p!=root) { p->isend=1; p=p->link; } } ``` 由于后缀自动机上所有路径能表示出原串的所有子串，所有以 一个有标记节点 结束的路径能表示出原串的所有后缀 于是可以从根节点DFS一遍，每次有分岔时优先走字典序比较小的转移，途中遇到有结束标记的节点则输出（原串总长度-DFS到当前节点经过长度+1），这样就完成了第一部分的任务（？） 第二部分的任务是找出排序后相邻两个后缀的最长公共前缀...我们发现在第一部分的DFS中正好排序后位置相邻的后缀访问顺序也是连着的，只需要求相邻两个访问的后缀的“LCA”就可以啦 贴代码~~走人~~ ~~鬼故事，进度条~~ ```cpp int lcp[MAXN],minn,cnt; void dfs(node *u,int len=0) { if(u->isend) { printf("%d ",totlen-len+1);//totlen为字符串总长 lcp[++cnt]=minn; //更新LCP信息 minn=len; } for(int x=0;x<sigma;x++) { if(u->next[x]) { if(len<minn)minn=len;//用来记录LCP长度 dfs(u->next[x],len+1); } } } ``` 呃...等等...为什么我TLE了？ 貌似这样搜索会做好多重复工作诶...（应该是 $ O(n^2) $ 的） 我们来想办法优化一下 由于不需要输出路径上的所有字符，所以只需要考虑路径长度 那么只有一种走法的路径就可以被压缩成一条边 也就是说这样的路径↓ $ \bigcirc ---1--> \bigcirc ---1--> \bigcirc ---1--> \bigcirc $ 可以压缩成这样↓ $ \bigcirc ---3--> \bigcirc $ 而不改变~~拓扑结构~~DFS结果 这...就是...传说中的...路径压缩？ ```cpp typedef pair<node*,int> pni; pni find(node *u) { if(!u->fast)return make_pair(u,0); pni _=find(u->fast); u->fast=_.first; u->fastlen+=_.second; return make_pair(u->fast,u->fastlen); } ``` 对比一下并查集的路径压缩（大雾） ```cpp typedef pair<int,int> pii; pii find(int x) { if(!pa[x])return make_pair(x,shift[x]); pii _=find(pa[x]); pa[x]=_.first; shift[x]^=_.second; return make_pair(pa[x],shift[x]); } ``` 好像没啥区别（大雾） 还需要预处理一下哪些边可以被压缩掉（动态求好像是错的，我不太明白为什么，可能是我写挂了）， 把代码扔进一开始的update函数里 ```cpp inline void update() { node *p=last; while(p!=root) { p->isend=1; p=p->link; } //更新部分↓ for(int i=1;i<=top;i++) { node *t=&pool[i],*q=0; if(t->isend)continue; int c=0; for(int ch=0;ch<sigma;ch++) { if(t->next[ch]) ++c,q=t->next[ch]; } if(c==1) { t->fast=q; t->fastlen=1; } } //更新部分↑ } ``` 最后在搜索的时候判一下能不能走被压缩的路径就好啦 ```cpp int lcp[MAXN],minn,cnt; void dfs(node *u,int len=0) { if(u->isend) { printf("%d ",totlen-len+1); lcp[++cnt]=minn; minn=len; } //更新部分↓ if(u->fast) { find(u); dfs(u->fast,len+u->fastlen); } //更新部分↑ else for(int x=0;x<sigma;x++) { if(u->next[x]) { if(len<minn)minn=len; dfs(u->next[x],len+1); } } } ``` 这样复杂度为什么是对的呢？ 我数学不好，不会证明，那就来感性理解一下 $ \bullet $ 经过“路径压缩”后的自动机构成一棵树 $ \bullet $ 叶子结点数（=原串后缀数）是 $ O(n) $ 的 $ \bullet $ 非叶子结点数（ $ \leq $ 叶子节点数-1）是 $ O(n) $ 的 $ \bullet $ 树的边数是 $ O(n) $ 的 $ \bullet $ 遍历这棵树是 $ O(n) $ 的 应该是这个意思吧QWQ反正跑得飞快QWQ 于是我就这么通过了 [UOJ#35 后缀排序](http://uoj.ac/problem/35) [通过记录](http://uoj.ac/submission/188201) 第一次写后缀自动机可能写挂了，欢迎dalao来hack P.S.这种方法貌似在LOJ（和洛谷）上会被卡内存...悲剧了...