P3975 [TJOI2015]弦论 SAM+right数组

2021-03-10 11:28

阅读：677

标签：字符证明 turn amp end bfs c++ one http

题意：

戳这里

分析：

\(sam\) 裸题，求第 \(k\) 大字符串

首先建出 \(sam\) 然后求出 \(siz[i]\) 表示 \(i\) 节点代表的串的 \(endpos\) 的集合大小

然后分情况讨论：

\(T==0\) 只统计本质不同的串的个数，所以所有点的 \(siz[i]\) 都置为 1
\(T==1\) \(siz[i]\) 不变

按照长度进行拓扑排序，因为 \(sam\) 上的点的 \(parent\) 树的 \(BFS\) 序等价于将 \(len\) 值类似于 \(sa\) 的基数排序后得到的序列一样（博主太笨，不会证明）

然后按照拓扑序，将儿子的 \(siz\) 值累加到父亲节点上，就得到经过每个点（即每种子串的出现次数），然后 \(DFS\) 得到第 \(k\) 个就可以了

代码:

#include

using namespace std;

namespace zzc
{
	const int maxn = 5e5+5;
	int len[maxnsum[trans[u][i]]) k-=sum[trans[u][i]];
			else
			{
				putchar(i+‘a‘);
				solve(trans[u][i],k);
				return;
			}	
		}
	}
	
	void work()
	{
		scanf("%s",ch+1);n=strlen(ch+1);scanf("%d%d",&T,&k);
		for(int i=1;i=1;i--) siz[link[sa[i]]]+=siz[sa[i]];
		for(int i=1;i=1;i--)
		{
			sum[sa[i]]=siz[sa[i]];
			for(int j=0;j

P3975 [TJOI2015]弦论 SAM+right数组

标签：字符证明 turn amp end bfs c++ one http

原文地址：https://www.cnblogs.com/youth518/p/14152595.html

上一篇：免费下载！Python密码学入门，这本书你Get到了么？

下一篇：Python实现1-100之和

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P3975 [TJOI2015]弦论 SAM+right数组
文章链接：http://soscw.com/essay/62734.html

亲，登录后才可以留言！

P3975 [TJOI2015]弦论 SAM+right数组

题意：

分析：

代码:

评论

热门文章

推荐文章

最新文章

置顶文章