2023 年上海市大学生程序设计竞赛 - 七月赛

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

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