탠덤 복사

탠덤 복사는 DNA에서 연속된 뉴클레오티드 하나 이상을 골라, 그 복사본을 원래 부분 바로 뒤에 붙이는 연산이다. 예를 들어 ATCG에서 ATC를 탠덤 복사하면 ATCATCG가 된다. 여기에 다시 탠덤 복사를 적용하면 ATCATTCG가 된다. 다음은 ATCG에서 시작하는 과정이다. ATCG $\Rightarrow$ ATCATCG $\Rightarrow$ ATCATTCG $\Rightarrow$ ATATCATTCG $\Rightarrow$ $\cdots$

ATCG는 탠덤 복사로 이 모든 문자열을 만들 수 있다고 한다. 단계마다 복사할 부분을 다르게 고르면 서로 다른 문자열을 만들 수 있고, 단계를 충분히 반복하면 무한히 많은 문자열을 만들 수 있다.

더 긴 부분을 복사할수록 비용이 많이 든다. ATCG에서 ATC를 복사하는 것은 ATCATCG에서 T 한 글자를 복사하는 것보다 비싸다. 따라서 복사하는 부분의 길이가 비용을 결정한다.

한 글자는 복사하기 쉬우므로, 연구실은 연속한 두 뉴클레오티드가 같지 않은 문자열을 저장한다. 예를 들어 ATTTG는 ATG에서 T를 두 번 복사해서 만들 수 있으므로, 연구실은 ATTTG 대신 ATG를 저장한다.

입력은 두 줄이다. 첫 줄은 원본 문자열 $s$, 둘째 줄은 목표 문자열 $t$이다. 두 문자열 모두 대문자 A부터 Z까지로 이루어지며, $1 \le |s|, |t| \le 2 \times 10^4$이다.

유효한 $s$의 부분 문자열의 개수를 한 줄에 출력한다.