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

\\n

对于一个字符串 $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$

\\n

定义一个字符串 $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\\\\}$

\\n

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

\\n

给定 $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|$

\\n

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

\\n

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

\\n

输入格式

\\n

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

\\n

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

\\n

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

\\n

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

\\n

输出格式

\\n

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

\\n\\n\\n

统计

递交统计

[集训队互测 2023day12]回文匹配（有多余文件）

信息

状态

开发

支持

登录