【小奇模拟赛】小奇的自动机

2016年5月21日1,5140

【题目背景】

小奇在研究后缀自动机时遇到了一个难题。

【问题描述】

定义:如果字符串A是字符串B的后缀,那么称B是A的XQ串。

小奇有n个只包含小写字母的字符串,编号为1-n,表示为Si。

接下来对于每个串Si,小奇想知道:对于小奇拥有的n个字符串,所有是Si的XQ串的编号集合(包括i)中第Ki小的编号。

【输入格式】

第1行1个整数n。

接下来n行,第i+1行包括1个字符串Si。

再接下来n行,第n+1+i行的整数表示Ki。

【输出格式】

输出n行,第i行表示对Si的询问的答案。

【样例输入】

3

cd

abcd

bcd

2

3

1

【样例输出】

2

-1

2

【数据范围】

对于20%的数据 n<=500,字符串总长<=1000;

对于50%的数据 K=1;

对于100%的数据 n<=100000,字符串总长<=300000。

题解

本题来自胜利一中Vampire

20%的数据

直接暴力好了

50%的数据

把所有的串反过来建个trie,那么某个串的结束结点的子树里的串就是所有的以该串为后缀的串

这部分数据只要求查询子树内的最小编号,用线段树维护dfs序即可

100%的数据

把区间最值改成区间K大,把线段树换成主席树即可

【更简单的做法】

由于可以离线,那么区间最值就能直接在trie上dp,而区间K大可以用线段树合并自底向上查询