【bzoj3230】相似子串

2015年7月9日2,6761

Description

Input

输入第1行,包含3个整数N,Q。Q代表询问组数。
第2行是字符串S。
接下来Q行,每行两个整数i和j。(1≤i≤j)。

Output

输出共Q行,每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串,则输出-1。

Sample Input

5 3
ababa
3 5
5 9
8 10

Sample Output

18
16
-1

HINT

样例解释
第1组询问:两个子串是“aba”,“ababa”。f = 32 + 32 = 18。
第2组询问:两个子串是“ababa”,“baba”。f = 02 + 42 = 16。
第3组询问:不存在第10个子串。输出-1。

数据范围
N≤100000,Q≤100000,字符串只由小写字母’a’~’z’组成

题解

求后缀数组,用height数组求出前i个后缀本质不同的子串个数,在这个数组中二分可以得到每次询问的俩个子串在原串中的位置

然后就是求这俩子串的最长公共前缀/最长公共后缀

这个预处理一下st表就能O1查询了

复杂度是nlogn的

 

  • 魔法炮2015年7月12日 下午8:49 回复

    用cin会狂RE……简直爆炸

    #1