题解：

对每种字符单独考虑。

对于字符$c$，首先除去$S$，$T$中非$c$字符，例如$S=ABABABABCABCABC$，$T=CBAA$，$c='A'$，处理后$S=A\#A\#A\#A\#\#A\#\#A\#\#$，$T=\#\#AA$。对于$k$，可以将$S$中的字母$c$向两边扩散$k$。例如当$k=3$，此时$S=AAAAAAAAAAAAAAA$。

考虑成功匹配时，$S$上的每个字符，与$T$上的的对应字符，位置的差是相等，将其中一个串反转，则匹配字符位置和相同，可以拆成多项式卷积形式。的对于字符$c$，构造 $F(x)=∑^n_{i=0}x^i[S_i=c]$，将 $T$串翻转操作后，$G(x)=∑^n_{i=0}x^i[T_i=c]$，若从$S$第$i$位开始$S$与$T$能匹配，则$F(x)*G(x)$在$x^i$项的系数应为$T$中$c$的数量。累加每种字符对应的$F(x)*G(x)$，若$x^i$项的系数为$|T|$，则该位置可以匹配。

struct Polynomial{
	const double PI=std::acos(-1.0);
	struct Complex{
		double x,y;
		Complex(double _x=0.0,double _y=0.0){
			x=_x;y=_y;
		}
		Complex operator-(const Complex &rhs)const{
			return Complex(x-rhs.x,y-rhs.y);
		}
		Complex operator+(const Complex &rhs)const{
			return Complex(x+rhs.x,y+rhs.y);
		}
		Complex operator*(const Complex &rhs)const{
			return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);
		}
	};
	int n;
	std::vector<Complex> c;
	Polynomial(int coef){
		int len=1<<(int)std::ceil(std::log2(coef+1));
		this->n=len;
		c.resize(len);
	}
	void modify(int pos,int val){c[pos]=Complex(val,0);}
	void change(std::vector<Complex> &y,int len){
		for(int i=1,j=len/2;i<len-1;i++){
			if(i<j)std::swap(y[i],y[j]);
			int k=len/2;
			while(j>=k){
				j-=k;
				k/=2;
			}
			if(j<k)j+=k;
		}
	}
	void fft(std::vector<Complex> &y,int len,int opt){
		change(y,len);
		for(int h=2;h<=n;h<<=1){
			Complex wn(cos(2.0*PI/h),sin(2.0*PI*opt/h));
			for(int j=0;j<len;j+=h){
				Complex w(1,0);
				for(int k=j;k<j+h/2;k++){
					Complex u=y[k];
					Complex t=w*y[k+h/2];
					y[k]=u+t;
					y[k+h/2]=u-t;
					w=w*wn;
				}
			}
		}
		if(opt==-1){
			for(int i=0;i<len;i++)y[i].x/=len;
		}
	}
	void mul(Polynomial b){
    	fft(c,n,1);
    	fft(b.c,b.n,1);
    	for(int i=0;i<n;i++)c[i]=c[i]*b.c[i];
    	fft(c,n,-1);
    }	
};
void solve(){
	int n,m,k;
	std::string s,t;
	std::cin>>n>>m>>k>>s>>t;
	std::set<char> S;
	for(auto c:s)S.insert(c);
	for(auto c:t)S.insert(c);
	std::vector<int> cnt(n+m-1);
	auto cal=[&](char c){
		Polynomial f(n+m-2),g(n+m-2);
		for(int i=0,lst=-k-1;i<n;i++){
			if(s[i]==c)lst=i;
			if(i-lst<=k)f.modify(i,1);
		}
		for(int i=n-1,lst=n+k;i>=0;i--){
			if(s[i]==c)lst=i;
			if(lst-i<=k)f.modify(i,1);
		}
		for(int i=0;i<m;i++)g.modify(i,(t[m-1-i]==c));
		f.mul(g);
		for(int i=0;i<n;i++)cnt[i]+=std::round(f.c[i].x);
	};
	for(auto c:S)cal(c);
	int ans=0;
	for(int i=0;i<n;i++)ans+=(cnt[i]==m);
	std::cout<<ans<<'\n';
}