URAL 1996 Cipher Message 3 FFT + KMP

題目大意：

就是現在給出一幅畫的存儲代碼為一組n個01串, 每個串的長度都是8, 現在有一串需要加密進去的01串, 長度為m個(n, m <= 250000)

現在可以将n個01串中的最後一個數字進行更改, 前7個01不能更改, 問是否能将這n個01串的末尾進行更改使得這個長度為m的加密消息出現在這個改動後的01串中

首先注意這題隻有目前7位相同時才有可能改成相同, 那麼可以先隻看每個01串的前7位進行KMP比對, 在O(n + m)的複雜度内找到所有可行的位置, 對于每個比對位置需要進行的改動數量, 其實就是兩個串之間的Hamming距離, 這個可以參見UVALive 4671的解法, 直接用FFT就可以在O(nlogn)的時間内得到, 那麼這個問題也就解決了

代碼如下：

Result  :  Accepted     Memory  :  29940 KB     Time  :  780 ms

/*
 * Author: Gatevin
 * Created Time:  2015/7/16 14:50:22
 * File Name: URAL1996.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

const double PI = acos(-1.0);

struct Complex
{
    double real, image;
    Complex(double _real, double _image)
    {
        real = _real;
        image = _image;
    }
    Complex(){}
};

Complex operator + (const Complex &c1, const Complex &c2)
{
    return Complex(c1.real + c2.real, c1.image + c2.image);
}

Complex operator - (const Complex &c1, const Complex &c2)
{
    return Complex(c1.real - c2.real, c1.image - c2.image);
}

Complex operator * (const Complex &c1, const Complex &c2)
{
    return Complex(c1.real*c2.real - c1.image*c2.image, c1.real*c2.image + c1.image*c2.real);
}

int rev(int id, int len)
{
    int ret = 0;
    for(int i = 0; (1 << i) < len; i++)
    {
        ret <<= 1;
        if(id & (1 << i)) ret |= 1;
    }
    return ret;
}

Complex A[1 << 19];
void FFT(Complex *a, int len, int DFT)
{
    for(int i = 0; i < len; i++)
        A[rev(i, len)] = a[i];
    for(int s = 1; (1 << s) <= len; s++)
    {
        int m = (1 << s);
        Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));
        for(int k = 0; k < len; k += m)
        {
            Complex w = Complex(1, 0);
            for(int j = 0; j < (m >> 1); j++)
            {
                Complex t = w*A[k + j + (m >> 1)];
                Complex u = A[k + j];
                A[k + j] = u + t;
                A[k + j + (m >> 1)] = u - t;
                w = w*wm;
            }
        }
    }
    if(DFT == -1) for(int i = 0; i < len; i++) A[i].real /= len, A[i].image /= len;
    for(int i = 0; i < len; i++) a[i] = A[i];
    return;
}

Complex N[1 << 19], M[1 << 19];
int inN[250010], inM[250010];

int next[250010];
vector <int> pos;//表示比對成功的開頭位置
int dif[250010];
int n, m;
void KMP()
{
    memset(next, 0, sizeof(next));
    for(int i = 1; i < m; i++)
    {
        int j = i;
        while(j > 0)
        {
            j = next[j];
            if((inM[i] >> 1) == (inM[j] >> 1))
            {
                next[i + 1] = j + 1;
                break;
            }
        }
    }
    pos.clear();
    for(int i = 0, j = 0; i < n; i++)
    {
        if((inM[j] >> 1) == (inN[i] >> 1))
        {
            j++;
        }
        else
        {
            while(j > 0)
            {
                j = next[j];
                if((inM[j] >> 1) == (inN[i] >> 1))
                {
                    j++;
                    break;
                }
            }
        }
        if(j == m) pos.push_back(i - m + 1);
    }
}

char tmp[10];

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%s", tmp);
            inN[i] = 0;
            for(int k = 0; k < 8; k++)
            {
                inN[i] <<= 1;
                if(tmp[k] == '1') inN[i] |= 1;
            }
        }
        for(int i = 0; i < m; i++)
        {
            scanf("%s", tmp);
            inM[i] = 0;
            for(int k = 0; k < 8; k++)
            {
                inM[i] <<= 1;
                if(tmp[k] == '1') inM[i] |= 1;
            }
        }
        if(n < m)
        {
            puts("No");
            continue;
        }
        KMP();
        if(pos.empty())
        {
            puts("No");
            continue;
        }
        //接下來FFT處理一下
        int len = 1;
        while(len <= n) len <<= 1;
        len <<= 1;
        
        for(int i = 0; i < n - m + 1; i++) dif[i] = m;
        
        //先算出都是1的比對位置
        for(int i = 0; i < n; i++)
            N[i] = Complex(inN[i] & 1, 0);
        for(int i = n; i < len; i++)
            N[i] = Complex(0, 0);
        for(int i = 0; i < m; i++)//将M序列反向過來求兩個串的Hamming距離(不同字元數)
            M[i] = Complex(inM[m - i - 1] & 1, 0);
        for(int i = m; i < len; i++)
            M[i] = Complex(0, 0);
        FFT(N, len, 1); FFT(M, len, 1);
        for(int i = 0; i < len; i++)
            N[i] = N[i] * M[i];
        FFT(N, len, -1);
        for(int i = 0; i < n - m + 1; i++) dif[i] -= (int)(N[i + m - 1].real + 0.5);
        
        //接下來算出都是0的位置
        for(int i = 0; i < n; i++)
            N[i] = Complex(1 - (inN[i] & 1), 0);
        for(int i = n; i < len; i++)
            N[i] = Complex(0, 0);
        for(int i = 0; i < m; i++)
            M[i] = Complex(1 - (inM[m - i - 1] & 1), 0);
        for(int i = m; i < len; i++)
            M[i] = Complex(0, 0);
        FFT(N, len, 1); FFT(M, len, 1);
        for(int i = 0; i < len; i++)
            N[i] = N[i] * M[i];
        FFT(N, len, -1);
        for(int i = 0; i < n - m + 1; i++) dif[i] -= (int)(N[i + m - 1].real + 0.5);
        
        int minDif = 1e9 + 7, ansPos = -1;
        puts("Yes");
        for(int i = 0, sz = pos.size(); i < sz; i++)
            if(minDif > dif[pos[i]])
                minDif = dif[pos[i]], ansPos = pos[i];
        printf("%d %d\n", minDif, ansPos + 1);
    }
    return 0;
}