这道题我一年前看到过。。。当时吓死了。。毫无思路。。
现在再看看。。发现好像是。。傻叉题？
https://www.spoj.pl/problems/TOP10/
首先注意到一个性质。。就是一些字符串按字典序排序后。。以某个字串开始的字符串是一个区间。。
那么对于这个题目。。我们将所有的字符串的后缀排序。。由于后缀的前缀就是子串。。所以对于一个询问
只需要用线段树来找区间前10大值就可以了。。
注意到显然不能直接将后缀提取再排序。。
可以使用hash搞。。复杂度NLogN^2。。
这道题我一年前看到过。。。当时吓死了。。毫无思路。。
现在再看看。。发现好像是。。傻叉题？
https://www.spoj.pl/problems/TOP10/
首先注意到一个性质。。就是一些字符串按字典序排序后。。以某个字串开始的字符串是一个区间。。
那么对于这个题目。。我们将所有的字符串的后缀排序。。由于后缀的前缀就是子串。。所以对于一个询问
只需要用线段树来找区间前10大值就可以了。。
注意到显然不能直接将后缀提取再排序。。
可以使用hash搞。。复杂度NLogN^2。。
排序这一步怎么做？
回复中国脑筋：hash乱搞。。二分算Lcp
回复WJBZBMR：我发现似乎可以用后缀数组？
回复中国脑筋:是啊。。所有串连起来中间用0隔开。。