2018.12.22 spoj7258 Lexicographical Substring Search(后缀自动机)

时间:2022-12-22 09:36:10

传送门

samsamsam基础题。

题意简述:给出一个串,询问第kkk大的本质不同的串。


然而这就是弦论的简化版。

我们把samsamsam建出来然后贪心选择就行了。

代码:

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2e5+5;
int n,q,K;
char s[N];
struct SAM{
	int last,tot,len[N],link[N],son[N][26],rk[N],cnt[N],sum[N];
	SAM(){last=tot=1;}
	inline void expand(int x){
		int p=last,np=++tot;
		len[last=np]=len[p]+1;
		while(p&&!son[p][x])son[p][x]=np,p=link[p];
		if(!p){link[np]=1;return;}
		int q=son[p][x],nq;
		if(len[q]==len[p]+1){link[np]=q;return;}
		len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q],link[q]=link[np]=nq;
		while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];
	}
	inline void topsort(){
		for(ri i=1;i<=tot;++i)++cnt[len[i]];
		for(ri i=1;i<=tot;++i)cnt[i]+=cnt[i-1];
		for(ri i=tot;i;--i)rk[cnt[len[i]]--]=i,sum[i]=1;
		for(ri i=tot;i;--i)for(ri j=0;j<26;++j)if(son[rk[i]][j])sum[rk[i]]+=sum[son[rk[i]][j]];
	}
	inline void query(){
		int p=1;
		while(K>0){
			for(ri i=0,v;i<26;++i){
				if(!(v=son[p][i]))continue;
				if(sum[v]>=K){--K,putchar('a'+i),p=v;break;}
				else K-=sum[v];
			}
		}
		puts("");
	}
}sam;
int main(){
	scanf("%s",s),n=strlen(s);
	for(ri i=0;i<n;++i)sam.expand(s[i]-'a');
	sam.topsort(),scanf("%d",&q);
	while(q--)scanf("%d",&K),sam.query();
	return 0;
}

2018.12.22 spoj7258 Lexicographical Substring Search(后缀自动机)的更多相关文章

  1. spoj 7258 Lexicographical Substring Search &lpar;后缀自动机&rpar;

    spoj 7258 Lexicographical Substring Search (后缀自动机) 题意:给出一个字符串,长度为90000.询问q次,每次回答一个k,求字典序第k小的子串. 解题思路 ...

  2. SPOJ SUBLEX - Lexicographical Substring Search 后缀自动机 &sol; 后缀数组

    SUBLEX - Lexicographical Substring Search Little Daniel loves to play with strings! He always finds ...

  3. SPOJ7258 SUBLEX - Lexicographical Substring Search&lpar;后缀自动机&rpar;

    Little Daniel loves to play with strings! He always finds different ways to have fun with strings! K ...

  4. SP7258 SUBLEX - Lexicographical Substring Search - 后缀自动机&comma;dp

    给定一个字符串,求本质不同排名第k小的子串 Solution 后缀自动机上每条路径对应一个本质不同的子串 按照 TRANS 图的拓扑序,DP 计算出每个点发出多少条路径 (注意区别 TRANS 图的拓 ...

  5. SPOJ Lexicographical Substring Search 后缀自动机

    给你一个字符串,然后询问它第k小的factor,坑的地方在于spoj实在是太慢了,要加各种常数优化,字符集如果不压缩一下必t.. #pragma warning(disable:4996) #incl ...

  6. SPOJ 7258 Lexicographical Substring Search &lbrack;后缀自动机 DP&rsqb;

    题意:给一个长度不超过90000的串S,每次询问它的所有不同子串中,字典序第K小的,询问不超过500个. 第一道自己做的1A的SAM啦啦啦 很简单,建SAM后跑kth就行了 也需要按val基数排序倒着 ...

  7. SP7258 SUBLEX - Lexicographical Substring Search&lpar;后缀自动机&rpar;

    传送门 解题思路 首先建\(sam\),然后在拓扑序上\(dp\)一下,把每个点的路径数算出来,然后统计答案时就在自动机上\(dfs\)一下,仿照平衡树那样找第\(k\)小. 代码 #include& ...

  8. &lbrack;SPOJ7258&rsqb;Lexicographical Substring Search

    [SPOJ7258]Lexicographical Substring Search 试题描述 Little Daniel loves to play with strings! He always ...

  9. 2018&period;12&period;21 bzoj3238&colon; &lbrack;Ahoi2013&rsqb;差异(后缀自动机)

    传送门 后缀自动机好题. 题意: 做法:samsamsam 废话 考虑翻转字串,这样后缀的最长公共前缀等于前缀的最长公共后缀. 然后想到parentparentparent树上面两个串的最长公共后缀跟 ...

随机推荐

  1. ibatis order by 防止sql注入

    (1) 排序控制 select TABLE_NAME, TABLESPACE_NAME from user_tables order by TABLE_NAME $ordertype$ Where t ...

  2. 还是要好好研究开源的php

    听说facebook是php写的,还是要静下心来好好研究一番的嘛,踏踏实实点点滴滴的做起来!加油

  3. spring环境搭建需要的插件-------Spring Tool Suite™ Downloads

    下载地址http://spring.io/tools/sts/all 上面的是集成了eclipse的,所以文件比较大,下面的是单独的插件,下载之后打开eclipse,help->installN ...

  4. Navi&period;Soft30&period;开放平台&period;百度&period;开发手册

    1系统简介 1.1功能简述 现在是一个信息时代,并且正在高速发展.以前获取信息的途径非常少,可能只有电视台,收音机等有限的来源,而现在的途径数不胜数,如:QQ,微信,官方网站,个人网站等等 本开发手册 ...

  5. Xamarin Android长度单位区别

    Xamarin Android长度单位区别 Android中长度单位有6种:px.in.mm.pt.dp/dip.sp.其中,px表示显示设备的一个像素:in表示显示设备的1英寸:mm表示显示设备的1 ...

  6. PHP之验证码识别

    首先推荐几篇有关验证码识别的文章,觉得不错 php实现验证码的识别(初级篇) 关于bp神经网格识别验证码 一.思路 碰见一个验证码,如果我们想要识别它,我们需要的是做什么呢? 我们先观察几个验证码.. ...

  7. java OPENCV 连通域, Imgproc&period;findContours 例子&comma;参数说明

    http://*.com/questions/29491669/real-time-paper-sheet-detection-using-opencv-in-android/ ...

  8. LinkCode 第k个排列

    http://www.lintcode.com/zh-cn/problem/permutation-sequence/# 原题 给定 n 和 k,求123..n组成的排列中的第 k 个排列. 注意事项 ...

  9. 【java】类的继承

    继承:特殊类拥有一般类的全部属性与行为. 继承好处:1.提高了代码的复用性2.让类与类之前产生了关系,有了这个关系才有多态的特性.继承是类和类之前的关系. 注意事项: 1.java只支持单继承,不支持 ...

  10. VMware12上安装CentOS7无法上网问题

    常安装使用VMware的搭建集群环境,VMare安装后虚拟机默认的是自动获取IP,有时候用的过程中突然XSHELL中断或者需要固定IP上网,遇到几次居然,但忘了步骤,总结一下,省的每次去找资料 环境配 ...