bzoj3439 kpm的MC密码 一种离线做法

雪舞喵做这题的时候脑补出了一个离线做法,并不需要可持久化线段树。

然而在网上一搜全是可持久化线段树的在线做法=。=

于是雪舞喵就写了写提交了一下,没想到居然AC了=。=

题目描述

给定 \(n\) 个小写字母组成的字符串,定义串 \(s_i\)\(s_j\) 的kpm串当且仅当 \(s_j\)\(s_i\) 的后缀。询问给定串中每个串的kpm串编号第 \(k_i\) 小的串的编号。

输入

第一行一个正整数 \(n\) ,接下来 \(n\) 行每行一个字符串。

接下来 \(n\) 行每行一个正整数 \(k_i\)

输出

输出 \(n\) 行每行一个整数,第 \(i\) 行的整数代表编号为 \(i\) 的串的kpm串中,编号第 \(k_i\) 小的串的编号,如果没有输出-1

数据范围

\(len\) 为所有串的长度和

\(n \le 10^5, len \le 3 \times 10^5\)


这题显然是要把串全部倒过来的,然后我们对这些串建一棵字典树。然后在字典树的每个终止节点上记录一下该串的编号, \(k_i\) 和一个临时变量size。

接下来我们在模拟一遍之前加串的过程,这次我们每经过一个终止节点,就把该节点上的size+=1,如果该节点的size等于 \(k_i\) 了,那么说明他的答案就是我们现在正在模拟添加的串。

唯一需要特殊处理的是可能有很多一样的串。我们在节点上用vector保存编号和 \(k_i\) 并在添加之后排好序即可。

时间复杂度 \(O(len)\) ,空间复杂度 \(O(len)\)

下面是代码

 

发表评论