分析：
这道题巧用了卷积的性质。
使用FFT来实现字符串匹配。
是一种高效的匹配方式，但缺陷在于，其必须按照每种字符分别匹配，有多少种字符，就要匹配多少次。
如果把模式串翻转，然后依次把某一字符设为1，其他字符设为0，此时做一次卷积，得到的结果AxAx就表示以x为终点匹配的字符数。
然后这道题需要字符串hash来判重，本来很经典的一道题这样一来就有点画蛇添足了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#define SF scanf
#define PF printf
#define MAXN 300000
using namespace std;
typedef long long ll;
int G=3;
int siz;
const double Pi=acos(-1);
struct cpx{double r,i;cpx() {}cpx(double _r,double _i):r(_r),i(_i) {}cpx operator * (const cpx &a) const{return cpx(r*a.r-i*a.i,r*a.i+i*a.r);}cpx operator + (const cpx &a) const{return cpx(r+a.r,i+a.i);}cpx operator - (const cpx &a) const{return cpx(r-a.r,i-a.i);}
};
void fft(cpx *a,int f,int N){int i,j,k;for(i=1,j=0;i<N;i++){for(int d=N;j^=d>>=1,~j&d;);if(i<j)swap(a[i],a[j]);}for(i=1;i<N;i<<=1){cpx wn(cos(Pi/i),f*sin(Pi/i));for(j=0;j<N;j+=i<<1){cpx w(1,0);for(k=0;k<i;k++,w=w*wn){cpx x=a[j+k],y=w*a[i+j+k];a[j+k]=x+y;a[i+j+k]=x-y;}}}if(f==-1)for(i=0;i<N;i++)a[i].r/=N;
}
cpx A[MAXN],B[MAXN];
int n,x,m,s;
int k,sum[MAXN],Cas;
char s1[MAXN],s2[MAXN];
set<ll> s3;
ll head[MAXN],seed=3,powx[MAXN];
int main(){powx[0]=1;for(int i=1;i<=100000;i++)powx[i]=powx[i-1]*seed;while(SF("%d",&k)!=EOF){Cas++;if(k==-1)break;s3.clear();memset(A,0,sizeof A);memset(B,0,sizeof B);SF("%s%s",s1,s2);int len1=strlen(s1);int len2=strlen(s2);siz=1;while(siz<=len1+len2)siz*=2;head[0]=(s1[0]=='a');for(int i=1;i<=len1;i++)head[i]=head[i-1]*seed+(s1[i]=='a');k=len2-k;for(int i=0;i<len1;i++)if(s1[i]=='a')A[i].r=1;for(int i=0;i<len2;i++)if(s2[i]=='a')B[len2-i-1].r=1;fft(A,1,siz);fft(B,1,siz);for(int i=0;i<siz;i++)A[i]=A[i]*B[i];fft(A,-1,siz);for(int i=len2-1;i<len1;i++)sum[i]=int(A[i].r+0.5);memset(A,0,sizeof A);memset(B,0,sizeof B);for(int i=0;i<len1;i++)if(s1[i]=='b')A[i].r=1;for(int i=0;i<len2;i++)if(s2[i]=='b')B[len2-i-1].r=1;fft(A,1,siz);fft(B,1,siz);for(int i=0;i<siz;i++)A[i]=A[i]*B[i];fft(A,-1,siz);int ans=0;for(int i=len2-1;i<len1;i++)sum[i]+=int(A[i].r+0.5);for(int i=len2-1;i<len1;i++){if(sum[i]>=k){ll pre;if(i==len2-1)pre=0;elsepre=head[i-len2];ll sx=head[i]-pre*powx[len2];s3.insert(sx);} }PF("Case %d: %d\n",Cas,s3.size());}
}