← 返回题目列表

Codeforces · 1081/H

H. 回文魔法

中文机器翻译题面 查看原题

在学习了一些关于回文的奇特算法后,Couti 发现回文非常有趣,所以他想用这个问题来挑战你。

Couti 有两个字符串 $$$A$$$ 和 $$$B$$$。因为他喜欢回文,所以他想选择 $$$a$$$ 作为 $$$A$$$ 的一些非空回文子串,并选择 $$$b$$$ 作为 $$$B$$$ 的一些非空回文子串。将它们连接起来,他将得到字符串$$$ab$$$。

Couti 认为他可以通过这种方式获得的字符串很有趣,因此他想知道他可以获得多少种不同的字符串。

输入

第一行包含单个字符串 $$$A$$$ ($$$1 \le |A| \le 2 \cdot 10^5$$$)。

第二行包含单个字符串 $$$B$$$ ($$$1 \le |B| \le 2 \cdot 10^5$$$)。

字符串 $$$A$$$ 和 $$$B$$$ 仅包含小写英文字母。

输出

第一行也是唯一一行应包含一个整数 - 可能的字符串数量。

示例

输入 #1

aa
aba

输出 #1

6

输入 #2

aaba
abaa

输出 #2

15

注意

在第一个示例中,可获得的字符串是

- “a”+“a”=“aa”,
- “aa”+“a”=“aaa”,
- “aa”+“aba”=“aaaba”,
- “aa”+“b”=“aab”,
- “a”+“aba”=“aaba”,
- “a”+“b”=“ab”。

在第二个示例中,可获取的字符串为“aa”、“aaa”、“aaaa”、“aaaba”、“aab”、“aaba”、“ab”、“abaa”、“abaaa”、“abaaba”、“abab”、“ba”、“baa”、“baba”、“bb”。

请注意,虽然“a”+“aa”=“aa”+“a”=“aaa”,但“aaa”只会计算一次。