【Luogu5108】仰望半月的夜空(后缀数组)
2024-10-18 00:05:46
【Luogu5108】仰望半月的夜空(后缀数组)
题面
题解
实名举报这题在比赛之前还不是这个样子的,还被我用SAM给水过去了
很明显求出\(SA\)之后就是按照\(SA\)的顺序从前往后考虑每一个长度,这样可以知道串是什么。
不过如果串相同要左端点最靠左,所以二分包含这个串的区间,用\(RMQ\)求出区间最小值即可。
(其实就是拿来复习SA板子的)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 400200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,sig;
char ch[MAX];
int S[MAX],tot,a[MAX],lg[MAX];
int t[MAX],x[MAX],y[MAX],rk[MAX],SA[MAX],hg[20][MAX],mn[20][MAX];
bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}
void GetSA()
{
int m=tot;
for(int i=1;i<=n;++i)t[x[i]=a[i]]++;
for(int i=1;i<=m;++i)t[i]+=t[i-1];
for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k+1;i<=n;++i)y[++p]=i;
for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;
for(int i=1;i<=m;++i)t[i]=0;
for(int i=1;i<=n;++i)t[x[y[i]]]++;
for(int i=1;i<=m;++i)t[i]+=t[i-1];
for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];
swap(x,y);x[SA[1]]=p=1;
for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;
if(p>=n)break;m=p;
}
for(int i=1;i<=n;++i)rk[SA[i]]=i;
for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(int i=1,j=0;i<=n;++i)
{
if(j)--j;
while(a[i+j]==a[SA[rk[i]-1]+j])++j;
hg[0][rk[i]]=j;
}
for(int j=1;j<=lg[n];++j)
for(int i=1;i+(1<<j)-1<=n;++i)
hg[j][i]=min(hg[j-1][i],hg[j-1][i+(1<<(j-1))]);
for(int i=1;i<=n;++i)mn[0][i]=SA[i];
for(int j=1;j<=lg[n];++j)
for(int i=1;i+(1<<j)-1<=n;++i)
mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<(j-1))]);
}
int lcp(int i,int j)
{
if(i==j)return 1e9;i=rk[i];j=rk[j];
if(i>j)swap(i,j);i+=1;int k=lg[j-i+1];
return min(hg[k][i],hg[k][j-(1<<k)+1]);
}
int RMQ(int i,int j)
{
if(i>j)swap(i,j);int k=lg[j-i+1];
return min(mn[k][i],mn[k][j-(1<<k)+1]);
}
int main()
{
sig=read();n=read();
if(sig==26)
{
scanf("%s",ch+1);n=strlen(ch+1);
for(int i=1;i<=n;++i)a[i]=ch[i]-96;
}
else for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)S[++tot]=a[i];
sort(&S[1],&S[n+1]);tot=unique(&S[1],&S[n+1])-S-1;
for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[tot+1],a[i])-S;
GetSA();
for(int i=1,p=1;i<=n;++i)
{
while(n-SA[p]+1<i)++p;
int l=p+1,r=n,ret=p;
while(l<=r)
{
int mid=(l+r)>>1;
if(lcp(SA[p],SA[mid])>=i)l=mid+1,ret=mid;
else r=mid-1;
}
printf("%d ",RMQ(p,ret));
}
puts("");return 0;
}
最新文章
- ASP.NET Core 中文文档 第四章 MVC(3.4)如何使用表单
- eclipse生成uml
- Docker Compose to CoreOS
- Visual Studio 中可执行文件中嵌入的清单文件
- 微软Asp.net MVC5生命周期流程图
- C++ VS2010 声明没有存储类或类型说明符
- POJ1037A decorative fence(动态规划+排序计数+好题)
- 学习manacher(最长公共回文串算法)
- csharp_ToJson的正确写法
- 【Shell脚本学习19】Shell while循环
- 网站压力测试工具webbench 安装与使用
- php 正则校验是否是域名
- Mysql 关键字-保留字(转帖)
- [CF] Final Exam Arrangement
- pt-tcp-model
- jmeter测试
- 算法-java代码实现希尔排序
- PHP中::的使用
- c++多态及实现原理
- ABP Zero项目入门踩坑
热门文章
- 常见 HTTP/FTP/WebSocket 错误代码大全 - 转
- Java 中 LinkedList 和 ArrayList 的区别
- Iterable接口
- [Oracle][Corruption]发生ORA00600[kdsgrp1]的时候,如何进行调查
- win8系统本地服务网络受限cpu占用率过高解决方案
- Mesos+Zookeeper+Marathon的Docker管理平台部署记录(1)
- PAT甲级题解-1066. Root of AVL Tree (25)-AVL树模板题
- poj1426 Find The Multiple(c语言巧解)
- github 学习心得
- poj 1723 SOLDIERS 带权中位数