首页 > 代码库 > 【bzoj2882】工艺 后缀自动机+STL-map
【bzoj2882】工艺 后缀自动机+STL-map
题目描述
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。
输入
第一行两个整数n，代表方块的数目。
第二行n个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。
输出
一行n个整数，代表最美观工艺品从左到右瑕疵度的值。
样例输入
10
10 9 8 7 6 5 4 3 2 1
样例输出
1 10 9 8 7 6 5 4 3 2
题解
后缀自动机+STL-map
表示并不会最小表示法，也不想学，于是用后缀自动机水了一发。
对于给定的原串，复制一遍后插入到后缀自动机中，然后再后缀自动机中找最小子串即可。
后缀自动机的具体实现过程与证明，可以参考：
陈老师PPT：https://wenku.baidu.com/view/fa02d3fff111f18582d05a81.html
大犇的blog：http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html
看起来挺复杂，实际上代码真心短。
由于字符集过大，所以需要用map储存边集。
#include <cstdio>#include <cstring>#include <map>#define N 1200010using namespace std;map<int , int> next[N];map<int , int>::iterator it;int a[N] , fa[N] , dis[N] , last = 1 , tot = 1;void ins(int c){ int p = last , np = last = ++tot; dis[np] = dis[p] + 1; while(p && !next[p][c]) next[p][c] = np , p = fa[p]; if(!p) fa[np] = 1; else { int q = next[p][c]; if(dis[q] == dis[p] + 1) fa[np] = q; else { int nq = ++tot; dis[nq] = dis[p] + 1 , next[nq] = next[q] , fa[nq] = fa[q] , fa[np] = fa[q] = nq; while(p && next[p][c] == q) next[p][c] = nq , p = fa[p]; } }}int main(){ int n , i , p = 1; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , ins(a[i]); for(i = 1 ; i < n ; i ++ ) ins(a[i]); while(n -- ) { it = next[p].begin(); printf("%d" , it->first); if(n) printf(" "); p = it->second; } return 0;}
【bzoj2882】工艺 后缀自动机+STL-map
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。