回文串 - ROJ

【题目描述】

令 $F(A,B)$ 表示选择一个串的非空前缀 $A$ 和串 $B$ 的非空后缀使得将串 $S$ 和串 $T$ 拼接起来之后是回文串的方案数。现在给定两个串 $A$ 和 $B$ ，令 $A_i$ 表示串 $A$ 的第 $i$ 长的后缀， $B_i$ 为串 $B$ 的第 $i$ 长的前缀。有 $Q$ 组询问，第 $i$ 组询问给定 $x_i$ 和 $y_i$ ，对每组询问求 $F(A_{x_i}，B_{y_i})$ 的值。

【输入】

第一行一个字符串 $str$ ，表示数据类型。接下来的两行分别表示字符串 $A$ 和 $B$ 。接下来一行一个正整数 $Q$ ，表示询问的个数。接下来 $Q$ 行，每行两个正整数 $x_i$ 和 $y_i$ 。

【输出】

输出 $Q$ 行，每行一个整数，表示这一组询问的答案。

【输入样例】

B
newionyzz
wyxioiwen
1
1 1

【输出样例】

【提示】

【样例解释】对于样例 1，共有以下 $16$ 种方案： $\{S=n,T=n\};\{S=n,T=en\};\{S=ne,T=n\};\{S=ne,T=en\}$ ； $\{S=ne,T=wen\};\{S=new,T=en\};\{S=new,T=wen\};\{S=new,T=iwen\}$ ； $\{S=new,T=ioiwen\};\{S=newi,T=wen\};\{S=newi,T=iwen\};\{S=newi,T=oiwen\}$ ； $\{S=newio,T=iwen\};\{S=newio,T=oiwen\};\{S=newio,T=ioiwen\};\{S=newion,T=oiwen\}$ 【数据规模】对于100%的数据，字符串中只出现小写字母。

子任务编号	子任务分值	$max(\|A\|,\|B\|)$	$Q$	数据类型
$1$	$10$	$≤40$	$≤200$	$C$
$2$	$15$	$≤2000$	$≤2000$	$A$
$3$	$7$	$≤10^5$	$=1$	$C$
$4$	$19$	$≤2000$	$≤2000$	$C$
$5$	$20$	$≤8×10^5$	$≤10^5$	$B$
$6$	$26$	$≤8×10^5$	$≤10^5$	$C$
$7$	$3$	$≤8×10^5$	$≤10^5$	$C$

数据类型， $A$ ：数据随机； $B$ ：串随机且 $|B|≤10^4$ ； $C$ ：无特殊性质。