아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

거의 같은 부분 문자열

시간 제한4초메모리 제한512 MB

요약
S에서 T'와 길이가 같고 정확히 한 글자만 다른 부분 문자열의 개수를 센다.
난이도

보통10점 중 6점

유형
문자열, 문자열 매칭, 해시맵, 이분 탐색
정답자
아직 제출이 없습니다

문제

불운한 이쿠타 군은 소중히 가지고 있던 문자열 TT를 바이러스 때문에 다른 문자열 T′T'로 바뀌고 말았다. 그 바이러스는 TT의 한 글자를 다른 글자로 바꾸었다는 것을 알고 있다. 즉 TT와 T′T'는 정확히 한 글자만 다르다. 이쿠타 군은 TT를 복원하기 위해, TT가 나타날 것이라고 생각되는 문서 SS를 준비했다. TT를 복원하기 위한 준비 작업으로 SS의 부분 문자열 중 TT와 일치할 가능성이 있는 것의 개수를 조사하려고 한다.

문자열 T′T'와 문서 SS가 주어진다. S=a_1a_2a_3...a_∣S∣S = a\_{1} a\_{2} a\_{3} ... a\_{|S|}의 길이 ∣T′∣|T'|인 부분 문자열 a_ka_k+1...a_k+∣T′∣−1(1≤k≤∣S∣−∣T′∣+1)a\_{k} a\_{k+1} ... a\_{k+|T'|-1}(1 \leq k \leq |S| - |T'| + 1) 중 T′T'와 비교해서 한 글자만 다른 것의 개수를 구하라.

입력

입력에 등장하는 각 변수는 다음 제약을 만족한다.

  • 1≤∣S∣≤300,0001 \leq |S| \leq 300,000

  • 1≤∣T′∣≤∣S∣1 \leq |T'| \leq |S|

출력

조건을 만족하는 부분 문자열의 개수를 한 줄에 출력하라.

예제3

  1. 예제 1

    입력
    abcbcdbc
    abc
    
    예상 출력
    2
    
  2. 예제 2

    입력
    aaaaaa
    aaaaaa
    
    예상 출력
    0
    
  3. 예제 3

    입력
    baaaaaaaa
    b
    
    예상 출력
    8