QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 1024 MB Total points: 100

# 5166. 回文匹配

统计

小 $\Delta$ 的字符串水平终于达到了普及组水平!他学会了求一个字符串在另一个字符串中的出现次数,但他意识到了这是为人熟知的原题,不能出到互测里。过了几天,小 $\Delta$ 开始学习提高组字符串算法,比如求一个字符串的最长回文子串,但这也是为人熟知的原题。但小 $\Delta$ 觉得只需要融合一下这两道题,就不算为人熟知的原题了,他出的题目如下。

对于一个字符串 $S=a_1a_2a_3\cdots a_k$,定义字符串的长度 $\left|S\right|=k$,定义 $S$ 的子串 $[l,r]$ 为 $S[l,r]=a_la_{l+1}\cdots a_{r}$,并定义其反转为 $S^R=a_ka_{k-1}\cdots a_1$

定义一个字符串 $S$ 的回文集合是其中所有回文串的位置的集合,也就是 $P(S)=\{(l,r)\in \mathbb Z^2\mid 1\leq l\leq r\leq \left|S\right|, S[l,r]=(S[l,r])^R\}$

定义两个字符串 $S,T$ 回文匹配,记为 $S\approx T$, 当且仅当 $P(S)=P(T)$

给定 $n$ 个字符串 $S_i$,令 $f(i,j)$ 为 $S_j$ 有多少个子串与 $S_i$ 回文匹配,也就是 $f(i,j)=\left|\{ (l,r) \in \mathbb Z^2\mid 1\leq l\leq r\leq \left|S_j\right|, S_j[l,r]\approx S_i\}\right|$

给定 $q$ 次询问,每次给定 $i,j$,求 $f(i,j)$

本题有两种输入方式,第一种是直接给出 $S_i$,第二种是把 $S_i$ 给定为其前面的某一个 $S_{f_i}$ 后面接上一个字符 $c_i$,见输入格式。

输入格式

第一行,三个整数 $T,n,q$

若 $T=0$,则接下来 $n$ 行,第 $i$ 行一个字符串 $S_i$

若 $T=1$,则接下来 $n$ 行,第 $i$ 行一个整数 $f_i$,和一个字符 $c_i$,若 $f_i=0$,则代表 $S_i=c_i$,否则代表 $S_i=S_{f_i}c_i$

接下来 $q$ 行,每行两个正整数 $i,j$,代表一组询问。

输出格式

$q$ 行,每行一个整数,代表一组询问的答案。

样例一

input

0 5 4
aba
acaba
acaca
aa
zzzzz
1 2
1 3
2 3
4 5

output

2
3
0
4

样例二

input

0 2 1
abca
jintianshikendejifengkuangxingqisivwowushi
1 2

output

35

样例解释

可惜这题没放到星期四考

样例三

input

1 7 4
0 a
1 b
2 a
1 a
4 b
5 a
0 a
7 6
3 6
2 5
4 6

output

4
1
1
1

数据范围与限制

时间限制 1.5s,空间限制 1GB

$T\in\{0,1\},1\leq n,q\leq 5\times 10^5$,$S_i$ 非空且只包含小写英文字符,$1\leq i,j\leq n$

当 $T=0$ 时,令 $L=\sum_{i=1}^n \left|S_i\right|$,保证 $L\leq 5\times 10^5$

当 $T=1$ 时,保证 $0\leq f_i\leq i-1$

子任务1(5分) $T=0,L\leq 1000$

子任务2(15分) $T=0$,所有 $\left|S_i\right|$ 全部相同。

子任务3(20分) $T=0,q=1$

子任务4(20分) $T=0$

子任务5(40分) 无特殊限制