Educational Codeforces Round 40 I. Yet Another String Matching Problem

http://codeforces.com/contest/954/problem/I

给你两个串s，p，求上一个串的长度为|p|的所有子串和p的差距是多少，两个串的差距就是每次把一个字符变成另一个字符的最小次数，字符最大到f

很明显，如果知道每两个串对应地方不相同的字符就能通过dfs/dsu解出来，那么如何快速的找到所有对应的不匹配的地方呢，

我们先单独考虑两个不同的字符，比如abada中取a，cba中取c，用二进制1代表选取的字符表示就是10101,100,我们用fft来加速这一过程

1　　2　　3　　4　　5　　　　1　　2　　3     -------> 　  　n-1　n-2　n-3

1　　0　　1　　0　　1　　　　1　　0　　0　　　　　　　1　　0 　　0

4　　3　　1

0　　0　　1

直接乘的话复杂度还是很高，我们把后一个串转一下变成001，这样如果要找最开始的串和p匹配是不是就系数是5看fft之后的系数是不是1，然后以此类推第二个是6，这样一遍fft就能求出所有情况，然后一共需要fft6*6次，复杂度(O(36*nlogn))

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod (1000000007)
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
//#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=125000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

struct cd
{
    double x,y;
    cd(double _x=0.0,double _y=0.0):x(_x),y(_y){}
    cd operator + (const cd &b)const
    {
        return cd(x+b.x,y+b.y);
    }
    cd operator - (const cd &b)const
    {
        return cd(x-b.x,y-b.y);
    }
    cd operator * (const cd &b)const
    {
        return cd(x*b.x-y*b.y,x*b.y+y*b.x);
    }
    cd operator / (const double &b)const
    {
        return cd(x/b,y/b);
    }
}a[N<<3],b[N<<3];
int rev[N<<3];
void getrev(int bit)
{
    for(int i=0; i<(1<<bit); i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
void fft(cd* a,int n,int dft)
{
    for(int i=0; i<n; i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int step=1; step<n; step<<=1)
    {
        cd wn(cos(dft*pi/step),sin(dft*pi/step));
        for(int j=0; j<n; j+=step<<1)
        {
            cd wnk(1,0);
            for(int k=j; k<j+step; k++)
            {
                cd x=a[k];
                cd y=wnk*a[k+step];
                a[k]=x+y;
                a[k+step]=x-y;
                wnk=wnk*wn;
            }
        }
    }
    if(dft==-1)for(int i=0; i<n; i++)a[i]=a[i]/n;
}
char s[N],p[N];
bool ok[N][7][7];
int fa[10];
int Find(int x)
{
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}
int main()
{
    scanf("%s%s",s+1,p+1);
    int n=strlen(s+1),m=strlen(p+1);
    int sz=0;
    while((1<<sz)<n)sz++;
    sz++;getrev(sz);
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
        {
            if(i==j)continue;
            for(int k=0;k<=(1<<sz);k++)a[k]=b[k]=0;
            for(int k=1;k<=n;k++)a[k]=(s[k]==i+'a');
            for(int k=1;k<=m;k++)b[n-k]=(p[k]==j+'a');
            fft(a,(1<<sz),1);fft(b,(1<<sz),1);
            for(int k=1;k<=(1<<sz);k++)a[k]=a[k]*b[k];
            fft(a,(1<<sz),-1);
            for(int k=0;k<=n-m;k++)ok[k][i][j]=(a[n+k].x>=0.5);
        }
    }
    for(int i=0;i<=n-m;i++)
    {
        for(int j=0;j<6;j++)fa[j]=j;
        int ans=0;
        for(int j=0;j<6;j++)
        {
            for(int k=0;k<6;k++)
            {
                if(j==k)continue;
                int fj=Find(j),fk=Find(k);
                if(ok[i][j][k]&&fj!=fk)fa[fj]=fk,ans++;
            }
        }
        printf("%d ",ans);
    }
    puts("");
    return 0;
}
/**********

**********/