Description：

给两个串 $S1$ 和 $S2$ ，如果满足 $\begin{align}\sum_{i=1}^{l2}[s1[j+i-1]\ne s2[i]]\le k\end{align}$ ，那么熟 $s2$ 在 $s1$ 的位置 $j$ 出现过，问 $s2$ 在 $s2$ 中出现了几次。

$1\le n \le200000,1\le k \le 100$

Solution：

$O(nk)$ 的复杂度可以过，可以枚举 $s1$ 的每个位置和 $s2$ 匹配，把 $s1$ 和 $s2$ 拼起来求后缀数组，用后缀数组找到 $LCP$ 并跳到 $LCP$ 的下一个，如果跳 $\le k$ 次就能跳到 $s2$ 末尾，那么就可以。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 2000010

int w;

char S[MAXL << 1],T[MAXL];

int l1,l2;

int t1[MAXL << 1],t2[MAXL << 1],c[MAXL << 1];

int sa[MAXL << 1],rnk[MAXL << 1],height[MAXL << 1];

#define rint register int

inline void makeSA(int n,int m)

{

	rint p;

	rint *x = t1,*y = t2;

	for(rint i = 1;i <= m;++i)c[i] = 0;

	for(rint i = 1;i <= n;++i)++c[x[i] = S[i]];

	for(rint i = 1;i <= m;++i)c[i] += c[i - 1];

	for(rint i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(rint k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(rint i = 1;i <= n;++i)y[i] = 0;

		for(rint i = n - k + 1;i <= n;++i)y[++p] = i;

		for(rint i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(rint i = 1;i <= m;++i)c[i] = 0;

		for(rint i = 1;i <= n;++i)++c[x[y[i]]];

		for(rint i = 1;i <= m;++i)c[i] += c[i - 1];

		for(rint i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		swap(x,y);

		p = 1;x[sa[1]] = 1;

		for(rint i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(rint i = 1;i <= n;++i)rnk[sa[i]] = i;

	rint k = 0; 

	for(rint i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		rint j = sa[rnk[i] - 1];

		while(j + k <= n && S[j + k] == S[i + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

int f[MAXL << 1][23];

inline void makeST(int n)

{

	for(rint i = 1;i < n;++i)f[i][0] = height[i + 1];

	for(rint k = 1;k <= 22;++k)

		for(rint i = 1;i < n;++i)

			f[i][k] = min(f[i][k - 1],f[i + (1 << (k - 1))][k - 1]);

	return;

}

inline int qry(int l,int r)

{

	if(l > r)swap(l,r);--r;

	rint len = log2(r - l + 1);

	return min(f[l][len],f[r - (1 << len) + 1][len]);

}

inline bool check(int p)

{

	rint p1 = p,p2 = 1;

	for(rint i = 0;i <= w;++i)

	{

		rint h = qry(rnk[p1],rnk[p2 + l1]);

		if(p2 + h - 1 >= l2)return true;

		p1 = p1 + h + 1;p2 = p2 + h + 1;

	}

	return false;

}

int main()

{

	freopen("mo.in","r",stdin);

	freopen("mo.out","w",stdout);

	scanf("%s%s%d",S + 1,T + 1,&w);

	l1 = strlen(S + 1);l2 = strlen(T + 1);

	for(rint i = 1;i <= l2;++i)S[l1 + i] = T[i];

	makeSA(l1 + l2,130);

	makeST(l1 + l2);

	rint cnt = 0;

	for(rint i = 1;i <= l1 - l2 + 1;++i)

	{

		if(check(i))++cnt;

	}

	cout << cnt << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}