305729: CF1081H. Palindromic Magic
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Palindromic Magic
题意翻译
给你两个字符串 $A$ 和 $B$。取 $A$ 的非空回文子串 $a$,$B$ 的非空回文子串 $b$。问 $a$、$b$ 组成的字符串 $ab$ 有多少种。题目描述
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](https://en.wikipedia.org/wiki/Palindrome), 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