#1702. 回文匹配

    ID: 1702 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>CTT赛事:contest1056来源:qoj.ac数据:公开样例字符串二分前缀和

回文匹配

回文匹配

题目描述

标题: 回文匹配 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

对于一个字符串 S=a1a2a3⋯ak,定义字符串的长度 |S|=k,定义 S 的子串 [l,r] 为 S[l,r]=alal+1⋯ar,并定义其反转为 SR=akak−1⋯a1

定义一个字符串 S 的回文集合是其中所有回文串的位置的集合,也就是 P(S)={(l,r)∈Z2∣1≤l≤r≤|S|,S[l,r]=(S[l,r])R}

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

给定 n 个字符串 Si,令 f(i,j) 为 Sj 有多少个子串与 Si 回文匹配,也就是 f(i,j)=|{(l,r)∈Z2∣1≤l≤r≤|Sj|,Sj[l,r]≈Si}|

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

本题有两种输入方式,第一种是直接给出 Si,第二种是把 Si 给定为其前面的某一个 Sfi 后面接上一个字符 ci,见输入格式。

输入格式

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

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

若 T=1,则接下来 n 行,第 i 行一个整数 fi,和一个字符 ci,若 fi=0,则代表 Si=ci,否则代表 Si=Sfici

接下来 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∈{0,1},1≤n,q≤5×105,Si 非空且只包含小写英文字符,1≤i,j≤n

当 T=0 时,令 L=∑i=1n|Si|,保证 L≤5×105

当 T=1 时,保证 0≤fi≤i−1

子任务1(5分) T=0,L≤1000

子任务2(15分) T=0,所有 |Si| 全部相同。

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

子任务4(20分) T=0

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

0 2 1
abca
jintianshikendejifengkuangxingqisivwowushi
1 2
35