Prefix와 Suffix

문자열 S의 부분 문자열 중 A로 시작하고 B로 끝나는 서로 다른 부분 문자열의 개수를 센다. A와 B는 부분 문자열 안에서 겹칠 수 있다.

보통6문자열해시맵문자열 매칭아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

문제

문자열 $S$ , $A$ , $B$ 가 주어진다.

$S$ 의 부분 문자열 중에서 $A$ 로 시작하고 $B$ 로 끝나는 것이 몇 가지인지 구하는 프로그램을 작성하시오. 부분 문자열은 $S$ 에서 연속한 구간을 뜻하고, 글자 구성이 같은 부분 문자열은 서로 다른 위치에서 나타나도 한 번만 센다. 한 부분 문자열 안에서 $A$ 가 차지하는 구간과 $B$ 가 차지하는 구간은 겹쳐도 된다.

입력

첫째 줄에 $S$ , 둘째 줄에 $A$ , 셋째 줄에 $B$ 가 주어진다. 세 문자열 모두 알파벳 소문자로만 이루어져 있고, 길이는 1 이상 2,000 이하이다.

출력

첫째 줄에 $A$ 로 시작하고 $B$ 로 끝나는 서로 다른 부분 문자열의 개수를 출력한다.

힌트

$S$ 가 abababab, $A$ 가 a, $B$ 가 b이면 조건을 만족하는 부분 문자열은 ab, abab, ababab, abababab 네 가지다.