UVALive4671 K-neighbor substrings 给定一个两个字符串A和B B为模式串。问A中有多少不同子串与B的距离小于k 所谓距离就是不同位的个数。
由于字符串只包含a和b 我们可以换做0和1 将B反转 进行大整数乘法（卷积） 就可以轻松得出不同的位数。只有FFT能在nlogn时间内完成大整数乘法。
要求不同的子串，再进行一次字符串散列即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<complex>
//使用FFT时注意精度问题和数组大小
using namespace std;
typedef long long int LL;
const double pi=acos(-1.0);
struct Complex {
double r, i;
Complex(double _r, double _i) {
r = _r;
i = _i;
}
double real()
{
return r;
}
double ii()
{
return i;
}
Complex operator + (const Complex &c) {
return Complex(c.r + r, c.i + i);
}
Complex operator - (const Complex &c) {
return Complex(r - c.r, i - c.i);
}
Complex operator * (const Complex &c) {
return Complex(c.r * r - c.i * i, c.r * i + c.i * r);
}
Complex operator / (const int &c) {
return Complex(r / c, i / c);
}
Complex(){}
};
void build(Complex _P[],Complex P[],LL n,LL m,LL curr,LL &cnt)
{
if(n==m){_P[curr]=P[cnt++];}
else {build(_P,P,n,m*2,curr,cnt);build(_P,P,n,m*2,curr+m,cnt);}
}
const LL maxn=300000;
void FFT(Complex P[],LL n,LL oper)//返回结果向左靠齐 最后结果除n
{
static Complex _P[maxn];
LL cnt=0;
build(_P,P,n,1,0,cnt);copy(_P,_P+n,P);
for(LL d=0;(1<<d)<n;d++)
{
LL m=1<<d;
LL m2=m*2;
double p0=pi/m*oper;
Complex unit_p0=Complex(cos(p0),sin(p0));
for(LL i=0;i<n;i+=m2)
{
Complex unit=Complex(1,0);
for(LL j=0;j<m;j++)
{
Complex &P1=P[i+j+m],&P2=P[i+j];
Complex t=unit*P1;
P1=P2-t;
P2=P2+t;
unit=unit*unit_p0;
}
}
}
}
void himult(Complex p1[],Complex p2[],LL n,Complex ans[])
{
FFT(p1,n,1);FFT(p2,n,1);
for(LL i=0;i<=n;i++)
ans[i]=p1[i]*p2[i];
FFT(ans,n,-1);
}
char a[131072*2],b[131072*2];
Complex av[131072*4],bv[131072*2+1],ans1[131072*2+1];
unsigned long long int ha[200000],xp[200000];
const int seed=3;
set<unsigned long long int >vise;
bool hash(int l,int r)
{
unsigned long long int nowv= ha[r+1]-ha[l]*xp[r-l+1];
if(vise.count(nowv)==0){vise.insert(nowv);return false;}
else return true;
}
int main()
{
freopen("t.txt","r",stdin);
xp[0]=1;
for(int i=1;i<=100000;i++)
xp[i]=xp[i-1]*seed;
int ii=0;
while(1)
{ ii++;
vise.clear();
int k;
scanf("%d",&k);
if(k==-1)break;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
scanf("%s%s",&a,&b);
int la=strlen(a),lb=strlen(b);
int len=1;
while(len<=la+lb)len<<=1;
for(int i=0;i<la;i++)
av[i]=Complex(a[i]=='a'?1:-1,0);
for(int i=la;i<=len;i++)av[i]=Complex(0,0);
for(int i=0;i<lb;i++)
bv[lb-i-1]=Complex(b[i]=='a'?1:-1,0);
for(int i=lb;i<=len;i++)
bv[i]=Complex(0,0);
memset(ans1,0,sizeof(ans1));
himult(av,bv,len,ans1);
int anss=0;
ha[0]=0;
for(int i=0;i<la;i++)
ha[i+1]=ha[i]*seed+a[i];
for(int i=0;i+lb<=la;i++)
{
if(hash(i,i+lb-1))continue;
int nue=(int)(ans1[i+lb-1].r/len+0.5);
if(lb-nue<=k*2)anss++;
}
printf("Case %d: %d
",ii,anss);
}
return 0;
}