#P1081H. Palindromic Magic
-
ID: 2935
Type: RemoteJudge
2000ms
1024MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Palindromic Magic
No submission language available for this problem.
Description
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 and . Since he likes palindromes, he would like to pick as some non-empty palindromic substring of and as some non-empty palindromic substring of . Concatenating them, he will get string .
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 ().
The second line contains a single string ().
Strings and contain only lowercase English letters.
The first and only line should contain a single integer — the number of possible strings.
Input
The first line contains a single string ().
The second line contains a single string ().
Strings and contain only lowercase English letters.
Output
The first and only line should contain a single integer — the number of possible strings.
Samples
Note
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.