영어 소문자로 구성된 두 문자열 \(A\)와 \(B\)에 대해서 다음의 조건이 만족될 때, 두 문자열은 “사실상 같다”고 한다.

1. \(A\)와 \(B\)의 길이가 같다.
2. 모든 가능한 정수 \(i\)와 \(j\)에 대해 \(A\)의 \(i\)번째와 \(j\)번째 글자가 같으면 \(B\)의 \(i\)번째와 \(j\)번째 글자도 같다.
3. 모든 가능한 정수 \(i\)와 \(j\)에 대해 \(A\)의 \(i\)번째와 \(j\)번째 글자가 다르면 \(B\)의 \(i\)번째와 \(j\)번째 글 자도 다르다.

예를 들어, \(A=aba\)와 \(B=pqp\)는 사실상 같은 문자열들이다. 하지만, \(A=abca\)와 \(B=abcb\)는 사실상 같은 문자열의 쌍이 아니다.

문자열 \(T\)와 \(P\)를 받아서 \(T\)의 연속된 부분문자열들 중 \(P\)와 사실상 같은 부분문자열의 개수를 계산하는 프로그램을 작성하라.

예를 들어, \(T=abababbab\)이고 \(P=pqp\)인 경우 \(T\)의 왼쪽부터 \(aba, bab, aba, bab, bab\)의 5개 의 부분문자열이 \(P\)와 사실상 같은 것들임을 알 수 있다. 

여러분은 다음 함수를 작성하여야 한다

• int findP( char T [], char P [], int N, int M ) : T는 길이 N+1인 배열(문자열)이다. P 는 길이 M+1인 배열이다. T와 P에는 각각 길이 N과 M인 영어 소문자 문자열이 저장되어 있 다. T와 P의 마지막 위치에는 ‘\0’이 저장되어 있다. findP는 T의 연속된 부분문자열들 중 P와 사실상 같은 부분문자열의 개수를 리턴해야 한다. 

구현 세부사항

다음의 함수 가 구현되어 있어야 한다. 

• int findP( char T [], char P [], int N, int M )

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

제한 조건

• \(1 \le N \le 1,000,000, 1 \le M \le N.\)

서브태스크 1 [ 8 points]

• \(N = M\)

서브태스크 2 [ 5 points]

• \(1 \le N \le 100\)

서브태스크 3 [ 12 points]

• \(1 \le N \le 2,000\)

서브태스크 4 [ 75 points]

• 원래 제한 조건 이외의 추가적인 제한 조건이 없음

line 1: 문자열 \(T\) 

line 2: 문자열 \(P\)