luogu1368 工艺
2019-08-16 07:48:49来源:博客园 阅读 ()
luogu1368 工艺
题目链接
思路
\(SAM\)练手题,将原串重复一遍插入到\(SAM\)中,然后贪心走长度为n的一个路径即可。
不用担心会直接走到终点,根据\(SAM\)的构造方式可以发现会先走到前面的路径。
代码
/*
* @Author: wxyww
* @Date: 2019-07-11 11:09:25
* @Last Modified time: 2019-07-11 11:20:42
*/
#include<cstdio>
#include<map>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 600000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int len,fa;
map<int,int>ch;
}SAM[N << 1];
int lst = 1,tot = 1;
void add(int c) {
int cur = ++tot,p = lst;
SAM[cur].len = SAM[p].len + 1;
while(p && !SAM[p].ch[c]) {
SAM[p].ch[c] = cur;
p = SAM[p].fa;
}
if(!p) SAM[cur].fa = 1;
else {
int q = SAM[p].ch[c];
if(SAM[q].len == SAM[p].len + 1) SAM[cur].fa = q;
else {
int clone = ++tot;
SAM[clone] = SAM[q];
SAM[clone].len = SAM[p].len + 1;
while(p && SAM[p].ch[c] == q) {
SAM[p].ch[c] = clone;
p = SAM[p].fa;
}
SAM[q].fa = SAM[cur].fa = clone;
}
}
lst = cur;
}
int a[N];
int main() {
int n = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= n;++i) add(a[i]);
for(int i = 1;i <= n;++i) add(a[i]);
int p = 1;
for(int i = 1;i <= n;++i) {
printf("%d ",SAM[p].ch.begin() -> first);
p = SAM[p].ch.begin() -> second;
}
return 0;
}
原文链接:https://www.cnblogs.com/wxyww/p/luogu1368.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash