5182. 回文文回

单点时限: 2.0 sec

内存限制: 512 MB

  • 回文串“是翻转后仍然不变的字符串,例如”qwq”,”abba”。
  • 一个字符串中的”回文子串“是指这个字符串一个具有回文性质 的子串,例如”qwq”中的回文字串有”q”,”w”,”q”,”qwq”。
  • 但你认为这些还是太简单了,于是你定义一个字符串中的”本质不同的回文子串“是去重后的回文子串,例如”qwq”中的”本质不同回文子串”有”q”,”w”,”qwq”。
  • 但这看起来还是没意思,于是你定义”本质不同公共回文子串“是两个字符串的”本质不同回文子串”的集合的交集,例如”qaqw”和”qwq”的”本质不同的公共回文子串”是”q”,”w”。

现在有 n 个小写字母字符串和 m 组询问,把字符串编号为 1n ,每组询问会询问字符串编号为 i,j ,”本质不同的公共回文子串“的数量。如果 i=j ,则是问编号为 i 的字符串有多少本质不同的公共回文子串。

输入格式

第一行两个正整数,分别依次表示 nm。 (2n105,1m105)
接下来 n 行,每行一个非空小写字母字符串。 (所有字符串长度总和 2.2×105)
再接下来 m 行,每行两个正整数 i,j 表示询问第 i 个字符串和第 j 个字符串的本质不同字符串数量。

输出格式

m 行,每行一个非负整数表示答案。

样例

Input
4 4
z
naxvbir
vxa
lslnzfumuvtsf
4 4
2 4
1 4
3 3
Output
11
2
1
3
Input
4 4
ajlltc
gicxwxbid
xw
mcugbdyd
4 4
1 2
4 4
4 3
Output
8
1
8
0
Input
4 4
ttld
dltjjustaat
jjustaatsujjjjustaat
dltjjustaats
4 2
1 2
2 4
4 2
Output
10
3
10
10
Input
4 4
ncrhgvhmjqp
wvkv
vk
y
4 3
3 4
3 4
2 4
Output
0
0
0
0

19 人解决,42 人已尝试。

27 份提交通过,共有 306 份提交。

6.6 EMB 奖励。

创建: 1 年,8 月前.

修改: 1 年,8 月前.

最后提交: 1 周,4 天前.

来源: N/A

题目标签