CF1081H.Palindromic Magic

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

After learning some fancy algorithms about palindromes, Chouti found palindromes very interesting, so he wants to challenge you with this problem.

Chouti has got two strings $A$ and $B$ . Since he likes palindromes, he would like to pick $a$ as some non-empty palindromic substring of $A$ and $b$ as some non-empty palindromic substring of $B$ . Concatenating them, he will get string $ab$ .

Chouti thinks strings he could get this way are interesting, so he wants to know how many different strings he can get.

输入格式

The first line contains a single string $A$ ( $1 \le |A| \le 2 \cdot 10^5$ ).

The second line contains a single string $B$ ( $1 \le |B| \le 2 \cdot 10^5$ ).

Strings $A$ and $B$ contain only lowercase English letters.

输出格式

The first and only line should contain a single integer — the number of possible strings.

输入输出样例

输入#1
```
aa
aba
```
输出#1
```
6
```
输入#2
```
aaba
abaa
```
输出#2
```
15
```

说明/提示

In the first example, attainable strings are

"a" + "a" = "aa",
"aa" + "a" = "aaa",
"aa" + "aba" = "aaaba",
"aa" + "b" = "aab",
"a" + "aba" = "aaba",
"a" + "b" = "ab".

In the second example, attainable strings are "aa", "aaa", "aaaa", "aaaba", "aab", "aaba", "ab", "abaa", "abaaa", "abaaba", "abab", "ba", "baa", "baba", "bb".

Notice that though "a"+"aa"="aa"+"a"="aaa", "aaa" will only be counted once.

首页