만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

해밍 거리와 쿼리

면접 대비

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

요약
이진 문자열 a와 b가 주어질 때, a의 부분 문자열과 b의 부분 문자열 사이의 해밍 거리를 묻는 질의에 답한다.
난이도

보통10점 중 5점

유형
누적 합, 문자열, 배열, 비트 연산
정답자
아직 제출이 없습니다

문제

길이가 같은 두 바이너리 문자열 ss와 tt의 해밍 거리는 값이 서로 다른 위치의 개수다. 예를 들어 "00111"과 "10101"의 해밍 거리는 2다.

바이너리 문자열 aa와 bb가 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • p1 p2 len: 두 부분 문자열 ap1ap1+1…ap1+len−1a_{p_1} a_{p_1+1} \ldots a_{p_1+len-1}과 bp2bp2+1…bp2+len−1b_{p_2} b_{p_2+1} \ldots b_{p_2+len-1}의 해밍 거리를 구해 출력한다.

문자열의 인덱스는 0부터 시작한다.

입력

첫째 줄에 바이너리 문자열 aa, 둘째 줄에 바이너리 문자열 bb가 주어진다. 두 문자열의 길이는 200,000 이하의 자연수다.

셋째 줄에 쿼리의 개수 qq (1≤q≤400,0001 \le q \le 400{,}000)가 주어진다. 이어지는 qq개의 줄에 쿼리 하나를 나타내는 p1p_1, p2p_2, lenlen이 공백으로 구분되어 주어진다. (1≤len1 \le len, 0≤p1≤∣a∣−len0 \le p_1 \le |a| - len, 0≤p2≤∣b∣−len0 \le p_2 \le |b| - len)

출력

각 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제6

  1. 예제 1

    입력
    101010
11110000
3
0 0 3
2 3 4
5 7 1
    예상 출력
    1
1
0

  2. 예제 2

    입력
    10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20
    예상 출력
    5
4
3
5
13

  3. 예제 3

    입력
    0
1
1
0 0 1
    예상 출력
    1

  4. 예제 4

    입력
    1111100000
1111100000
4
0 0 10
0 5 5
5 0 5
3 3 4
    예상 출력
    0
5
5
0

  5. 예제 5

    입력
    1111111111111111111111111111111111111111111111111111111111111111111111
0000000000000000000000000000000000000000000000000000000000000000000000
5
0 0 70
0 0 64
6 6 64
0 6 63
69 69 1
    예상 출력
    70
64
64
63
1

  6. 예제 6

    입력
    1110010011000110000000011100110011101101000101100000011110011011010000001100100110110011000100001101110000001110101001000001101000
0101111100001010000111000011001011000111000101100011001101010101100000111111100101000111011000111011101001010001100100111011111100
8
0 0 130
1 0 129
0 1 129
63 1 65
64 64 66
65 3 64
2 66 64
129 129 1
    예상 출력
    67
56
63
31
35
31
34
0