UVALive - 4671 K-neighbor substrings (FFT+哈希)

题意:海明距离的定义:两个相同长度的字符串中不同的字符数.现给出母串A和模式串B,求A中有多少与B海明距离<=k的不同子串

分析:将字符a视作1,b视作0.则A与B中都是a的位置乘积是1.现将B逆置,并设B的长度为n,令\(C(n+k-1)= \sum_{i=0}^{n-1}A_{i+k}*B_{n-i-1}\),表示母串A中从位置k开始,长度为n的子串与B中字符都是'a'的位置的数目,可以通过FFT运算得到.再对字符'b'做一次同样的运算,\(ans[i]\)统计母串A中以i结尾的子串与B相同字符的个数.

设A的长度为m,则一共有\(m-n+1\)个子串,若\(n-ans[i] \leq k\),则盖子串符合条件,但本题需要求不同的子串,所以将母串哈希掉,将符合要求的哈希值存在集合中去重.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 4e5 + 10;

const double PI = acos(-1.0);

struct Complex{

    double x, y;

    inline Complex operator+(const Complex b) const {

        return (Complex){x +b.x,y + b.y};

    }

    inline Complex operator-(const Complex b) const {

        return (Complex){x -b.x,y - b.y};

    }

    inline Complex operator*(const Complex b) const {

        return (Complex){x *b.x -y * b.y,x * b.y + y * b.x};

    }

} va[MAXN * 2 + MAXN / 2], vb[MAXN * 2 + MAXN / 2];

int lenth = 1, rev[MAXN * 2 + MAXN / 2];

int N, M;   // f 和 g 的数量

    //f g和 的系数

    // 卷积结果

    // 大数乘积

int f[MAXN],g[MAXN];

vector<LL> conv;

vector<LL> multi;

//f g

void init()

{

    int tim = 0;

    lenth = 1;

    conv.clear(), multi.clear();

    memset(va, 0, sizeof va);

    memset(vb, 0, sizeof vb);

    while (lenth <= N + M - 2)

        lenth <<= 1, tim++;

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

        rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (tim - 1));

}

void FFT(Complex *A, const int fla)

{

    for (int i = 0; i < lenth; i++){

        if (i < rev[i]){

            swap(A[i], A[rev[i]]);

        }

    }

    for (int i = 1; i < lenth; i <<= 1){

        const Complex w = (Complex){cos(PI / i), fla * sin(PI / i)};

        for (int j = 0; j < lenth; j += (i << 1)){

            Complex K = (Complex){1, 0};

            for (int k = 0; k < i; k++, K = K * w){

                const Complex x = A[j + k], y = K * A[j + k + i];

                A[j + k] = x + y;

                A[j + k + i] = x - y;

            }

        }

    }

}

void getConv(){             //求多项式

    init();

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

        va[i].x = f[i];

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

        vb[i].x = g[i];

    FFT(va, 1), FFT(vb, 1);

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

        va[i] = va[i] * vb[i];

    FFT(va, -1);

    for (int i = 0; i <= N + M - 2; i++)

        conv.push_back((LL)(va[i].x / lenth + 0.5));

}

char s1[100005],s2[100005];

LL res[MAXN];

const int seed = 3;

LL dig[MAXN],Hash[MAXN];

set<LL> dp;

void pre(){

    dig[0] =1;

    for(int i=1;i<=100005;++i){

        dig[i] = dig[i-1]*seed;

    }

}

LL getHash(int L ,int R){

    if(L==0) return Hash[R];

    return Hash[R] - Hash[L-1]*dig[R-L+1];

}

int main()

{

    #ifndef ONLINE_JUDGE

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

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

    #endif

    pre();

    int k,cas=1;

    while(scanf("%d",&k)==1){

        if(k==-1) break;

        memset(res,0,sizeof(res));

        dp.clear();

        scanf("%s",s1);

        scanf("%s",s2);

        int len1 = strlen(s1), len2 = strlen(s2);

        N = len1, M  = len2;

        for(int i=0;i<len1;++i){

            if(s1[i]=='a') f[i] = 1;

            else f[i] = 0;

        }

        for(int i=0;i<len2;++i){

            if(s2[len2-i-1]=='a') g[i] = 1;

            else g[i] = 0;

        }

        getConv();

        int sz =conv.size();

        for(int i=len2-1;i<sz;++i){

            res[i] += conv[i];

        }

        for(int i=0;i<len1;++i){

            if(s1[i]=='b') f[i] = 1;

            else f[i] = 0;

        }

        for(int i=0;i<len2;++i){

            if(s2[len2-i-1]=='b') g[i] = 1;

            else g[i] = 0;

        }

        getConv();

        sz =conv.size();

        for(int i=len2-1;i<sz;++i){

            res[i] += conv[i];

        }

        //Hash

        Hash[0] = s1[0]-'a'+1;

        for(int i=1;i<len1;++i){

            Hash[i] = Hash[i-1]*seed + s1[i]-'a'+1;

        }

        for(int i=len2-1;i<len1;++i){

            LL now = getHash(i-len2+1,i);

            if(len2-res[i]<=k){

                dp.insert(now);

            }

        }

        printf("Case %d: %d\n",cas++,(int)dp.size());

    }

    return 0;

}

巴特西

UVALive - 4671 K-neighbor substrings (FFT+哈希)

最新文章

热门文章