문자열 찾기

영어 소문자로 구성된 두 문자열 $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와 사실상 같은 부분문자열의 개수를 리턴해야 한다.

• $1 ≤ N ≤ 1\\,000\\,000$, $1 ≤ M ≤ N$.