BZOJ3998 TJOI2015弦论(后缀自动机)
2024-09-01 14:37:42
先考虑相同子串视为一个。按SAM的拓扑序预处理出从每个节点开始能得到多少个本质不同子串(注意虽然一个节点对应多个子串,但到达该点时当前的子串显然是确定为其中一个的),然后按位贪心即可。
相同子串视为多个的做法也没有本质区别。求出每个节点的right集合大小,同样预处理出从每个节点开始能得到多少个子串按位贪心。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int 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<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,op,son[N][26],fail[N],len[N],size[N],id[N],tmp[N],cnt=1,last=1;
ll k,f[N],g[N];
char s[N];
void ins(int c)
{
int x=++cnt,p=last;last=x;len[x]=len[p]+1;size[x]=1;
while (!son[p][c]) son[p][c]=x,p=fail[p];
if (!p) fail[x]=1;
else
{
int q=son[p][c];
if (len[p]+1==len[q]) fail[x]=q;
else
{
int y=++cnt;
len[y]=len[p]+1;
memcpy(son[y],son[q],sizeof(son[q]));
fail[y]=fail[q],fail[q]=fail[x]=y;
while (son[p][c]==q) son[p][c]=y,p=fail[p];
}
}
}
void dfs(int k,ll x)
{
x-=g[k];
if (x==0) return;
for (int i=0;i<26;i++)
if (x<=f[son[k][i]])
{
putchar(i+'a');
dfs(son[k][i],x);
return;
}
else x-=f[son[k][i]];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
scanf("%s",s+1);n=strlen(s+1);
cin>>op>>k;
for (int i=1;i<=n;i++) ins(s[i]-'a');
for (int i=1;i<=cnt;i++) tmp[len[i]]++;
for (int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
for (int i=1;i<=cnt;i++) id[tmp[len[i]]--]=i;
for (int i=cnt;i>=1;i--) size[fail[id[i]]]+=size[id[i]];
for (int i=2;i<=cnt;i++) if (op==0) g[i]=1;else g[i]=size[i];
for (int i=cnt;i>=1;i--)
{
int x=id[i];f[x]=g[x];
for (int j=0;j<26;j++) f[x]+=f[son[x][j]];
}
if (f[1]<k) {cout<<-1;return 0;}
dfs(1,k);
return 0;
}
最新文章
- Opencv 2.4.9在Ubuntu下的配置与安装
- andorid
- .NET垃圾回收笔记
- GitHub 添加 SSH keys
- IMDB TOP 250爬虫
- C# Ioc 接口注册实例以及注入MVC Controller
- 转载 git Unknown SSL protocol error in connection to github.com:443
- 3.1 PCI设备BAR空间的初始化
- JS中回调函数的写法
- html标签分类
- php 将图片转成base64
- base64 压缩上传上传图片
- java集合框架(1) hashMap 简单使用以及深度分析(转)
- jmeter正则表达式提取器多模块相互调用
- Leetcode 题解 First Missing Positive
- 阿里云RDS数据库备份文件恢复到本地数据库
- 魔兽私服TrinityCore 运行调试流程
- (1)RGB-D点云生成
- putty如何退出全屏模式
- spring-security-4 (3)spring security过滤器的创建与注册原理