41 lines
No EOL
913 B
Python
41 lines
No EOL
913 B
Python
import sys
|
|
|
|
input_data = sys.stdin.read().split()
|
|
s_len = int(input_data[0])
|
|
t_len = int(input_data[1])
|
|
k = int(input_data[2])
|
|
S = input_data[3]
|
|
T = input_data[4]
|
|
|
|
mask_S = {}
|
|
for char in "ACGT":
|
|
valid = [0] * s_len
|
|
|
|
last = -1000000
|
|
for i in range(s_len):
|
|
if S[i] == char:
|
|
last = i
|
|
if i - last <= k:
|
|
valid[i] = 1
|
|
|
|
last = 1000000
|
|
for i in range(s_len - 1, -1, -1):
|
|
if S[i] == char:
|
|
last = i
|
|
if last - i <= k:
|
|
valid[i] = 1
|
|
|
|
b = bytearray((s_len + 7) // 8)
|
|
for i in range(s_len):
|
|
if valid[i]:
|
|
b[i // 8] |= (1 << (i % 8))
|
|
|
|
mask_S[char] = int.from_bytes(b, byteorder='little')
|
|
|
|
ans_mask = (1 << (s_len - t_len + 1)) - 1
|
|
ans_mask &= mask_S[T[0]]
|
|
|
|
for j in range(1, t_len):
|
|
ans_mask = (ans_mask << 1) & mask_S[T[j]]
|
|
|
|
print(ans_mask.bit_count()) |