Description：

串 $S$ 和 $T$ 只包含 $AGCT$ 四种字符。要求每个字符只能和距离他不超过 $k$ 的相同字符匹配，求 $T$ 在 $S$ 中匹配的数量。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

这个题字符集非常小，只有四个，所以可以分别考虑，那么我们就可以求出在每个位置，只考虑某个字符，最大匹配的字符个数，然后累加，如果等于 $|T|$ ，那么就找到了一个位置，求最大匹配可以用 $FFT$ ，还是先按套路把 $T$ 翻转，然后对于每个 $S_i$ ，如果距离不超过 $k$ 有这么一个字符，那么 $a[i]=1$ ，对于每个 $T_i$ ，如果他就是这个字符，那么 $b[i]=1$ ，然后把两个多项式卷积起来就是这个字符的贡献。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

char getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	return c;

}

int ls,lt,k;

#define MAXN 800010

char s[MAXN],t[MAXN];

#define INF 0x3f3f3f3f

int res[MAXN];

int rev[MAXN];

const double PI = acos(-1);

struct comp

{

	double r,i;

	comp(double r_ = 0.0,double i_ = 0.0){r = r_;i = i_;}

}a[MAXN],b[MAXN];

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i > rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

		for(int j = 0;j < l;j += i)

		{

			comp w = (comp){1,0};

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

void calc(char ch,int l)

{

	memset(a,0,sizeof(a));

	memset(b,0,sizeof(b));

	for(int i = 0,last = -INF;i < ls;++i)

	{

		if(s[i] == ch)last = i;

		if(i - last <= k)a[i].r = 1;

	}

	for(int i = ls - 1,last = INF;i >= 0;--i)

	{

		if(s[i] == ch)last = i;

		if(last - i <= k)a[i].r = 1;

	}

	for(int i = 0;i < lt;++i)

	{

		if(t[i] == ch)b[i].r = 1;

	}

	FFT(a,l,1);FFT(b,l,1);

	for(int i = 0;i < l;++i)a[i] = a[i] * b[i];

	FFT(a,l,-1);

	for(int i = 0;i < l;++i)res[i] += int(a[i].r + 0.5);

	return;

}

int main()

{

	scanf("%d%d%d",&ls,&lt,&k);

	for(int i = 0;i < ls;++i)s[i] = getc();

	for(int i = 0;i < lt;++i)t[i] = getc();

	for(int i = 0,j = lt - 1;i < j;++i,--j)swap(t[i],t[j]);

	int l = 0,len = 1;

	for(;len <= ls * 2;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	calc('A',len);calc('G',len);calc('C',len);calc('T',len);

	int ans = 0;

	for(int i = lt - 1;i < len;++i)

	{

		if(res[i] == lt)++ans;

	}

	cout << ans << endl;

	return 0;

}