공통인 회문
시간 제한2초메모리 제한512 MB
S의 부분 문자열과 T의 부분 문자열이 서로 같으면서 회문인 구간 쌍 (i,j,k,l)의 개수를 센다. 두 문자열 길이는 최대 50,000이다.
문제
ICPC에서 좋은 성적을 거두려면 수행이 필요하다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수행을 하기로 했다.
오늘의 수행은 문자열에서 회문을 찾아, 글에서 숨은 메시지를 읽어내는 능력을 기르는 것이다. 회문이 많이 있을 수 있으니, 찾는 김에 개수도 세어 보려 한다.
두 문자열 S, T가 주어질 때, 다음 조건을 만족하는 정수 쌍 (i, j, k, l)의 개수를 구하려 한다.
- 1 ≤ i ≤ j ≤ (S의 길이).
- 1 ≤ k ≤ l ≤ (T의 길이).
- S의 i번째 문자부터 j번째 문자까지 잘라낸 부분 문자열은 T의 k번째 문자부터 l번째 문자까지 잘라낸 부분 문자열과 같고, 이들은 회문(왼쪽에서 읽어도 오른쪽에서 읽어도 같은 문자열)이다.
입력
S
T
문자열 S, T는 모두 길이가 1 이상 50,000 이하이며, 알파벳 대문자로 이루어진다.
출력
조건을 만족하는 정수 쌍 (i, j, k, l)의 개수를 한 줄에 출력한다.