#P4442. [Swerc2015]Text Processor

    ID: 3647 传统题 1000ms 512MiB 尝试: 16 已通过: 3 难度: 9 上传者: 标签>CF2800省选/NOI-后缀自动机endpos 等价类Link-Cut Tree差分树状数组分段多项式扫描中维护贡献

[Swerc2015]Text Processor

题目描述

给你一个字符串,每次询问你一个长度为 ww 的区间 [i,i−w+1][i,i-w+1] 中不同的子串个数

输入格式

第一行一个字符串 DD。

第二行两个正整数 QQ 和 ww,分别表示询问总数和所有询问的区间长度。

接下来 QQ 行,每行一个正整数,表示询问区间的起始位置。

输出格式

对于每个询问,输出一个整数,表示该区间的不同子串个数。

acat
2 3
1
2
5
6
portoisamazing
2 7
6
3
26
28

样例解释:

在第一个样例中:

第一个询问询问区间 [1,3]→(aca)[1,3]\to (\texttt{aca}) 该区间有5个不同的子串 (a,c,ac,ca,aca)\texttt{(a,c,ac,ca,aca)}

第二个询问询问区间 [2,4]→(cat)[2,4]\to (\texttt{cat}) 该区间有6个不同的子串 (c,a,t,ca,at,cat)\texttt{(c,a,t,ca,at,cat)}

数据规模与约定

对于 100%100\% 的数据,$1\le W\le |D|\le 10^5,1\le Q\le 10^5,1\le i\le |D|-w+1$。