转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove

题意 ：给出两个串A ， B，每个串是若干个byte，A串的每个byte的最后一个bit是可以修改的。问最少修改多少，使得B串是A的一个子串。

2013年NEERC的题。。。。。。。感觉[buaa]sd0061教我做这题。

NEERC是毛子题，但是这套题感觉除了题面很难读之外，并不是很难。。。

目前为止，J题貌似全队都没看题，E题还在WA中，其它题都没啥问题。

做法：前7位都是不能修改的，所以要完全匹配，那么先按前7位KMP一下，记录匹配的位置。之后就是统计以这些位置开始，需要修改多少位，然后 取最小值。

所以提取出最后一个bit，成了两个01串，统计hamming distance。

记得若干年前就和队友讨论过这个问题，不过当时不是01串，觉得不可在n * m之内解决，然后 就放弃了。结果这个01串是可以 在nlgn解决 的。吓傻。。

两个01串a , b。将b反转之后，求一次卷积，便可以得到a串中以i为起始位置，与b进行匹配有多少个位置同为1。

那么接下来把a,b的01反转一下，再求一次卷积，就可以得到原串中为多少个位置同为0。就得到了hamming距离。

卷积求的是c[i + j] = a[i] * b[j]。由于我们将b进行了反转，所以a串中以i为起始位置的。

c[i + m - 1] = a[i + 0] * b[m - 0 - 1] + a[i + 1] * b[m - 1 - 1] + …… a[i + j] * b[m - j - 1] + …… a[i + m - 1] * b[m - (m - 1) - 1]。

如果a , b中同为1,乘积为1,否则为0,这样就统计出了有多少位同为1了。吓傻。。。太神了。

预处理出这个之后，再枚举之前KMP所得到的匹配位置 就可以了。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <vector>

#include <algorithm>

#include <queue>

#include <set>

using namespace std;

typedef long long LL;

typedef pair<int , int> pii;

const int N = 1000005;

//FFT copy from kuangbin

const double pi = acos (-1.0);

// Complex  z = a + b * i

struct Complex {

    double a, b;

    Complex(double _a=0.0,double _b=0.0):a(_a),b(_b){}

    Complex operator + (const Complex &c) const {

        return Complex(a + c.a , b + c.b);

    }

    Complex operator - (const Complex &c) const {

        return Complex(a - c.a , b - c.b);

    }

    Complex operator * (const Complex &c) const {

        return Complex(a * c.a - b * c.b , a * c.b + b * c.a);

    }

};

//len = 2 ^ k

inline void change (Complex y[] , int len) {

    for (int i = 1 , j = len / 2 ; i < len -1 ; i ++) {

        if (i < j) swap(y[i] , y[j]);

        int k = len / 2;

        while (j >= k) {

            j -= k;

            k /= 2;

        }

        if(j < k) j += k;

    }

}

// FFT

// len = 2 ^ k

// on = 1  DFT    on = -1 IDFT

inline void FFT (Complex y[], int len , int on) {

    change (y , len);

    for (int h = 2 ; h <= len ; h <<= 1) {

        Complex wn(cos (-on * 2 * pi / h), sin (-on * 2 * pi / h));

        for (int j = 0 ; j < len ; j += h) {

            Complex w(1 , 0);

            for (int k = j ; k < j + h / 2 ; k ++) {

                Complex u = y[k];

                Complex t = w * y [k + h / 2];

                y[k] = u + t;

                y[k + h / 2] = u - t;

                w = w * wn;

            }

        }

    }

    if (on == -1) {

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

            y[i].a /= len;

        }

    }

}

int n , m , a[N] , b[N];

int c[N] , d[N] , next[N] , p[N];

char str[10];

void get_next (int *a , int l) {

    int i = 0 , j = -1;

    next[i] = j;

    while (i < l) {

        if (j == -1 || a[i] == a[j]) {

            i ++; j ++;

            next[i] = j;

        }

        else j = next[j];

    }

}

int pos[N] , cnt;

void match (int *a , int la , int *b , int lb) {

    int i = 0 , j = 0;

    while (i < la) {

        if (j == -1 || a[i] == b[j]) {

            i ++;j ++;

            if (j == lb) {

                pos[cnt ++] = i - lb;

                j = next[j];

            }

        }

        else j = next[j];

    }

}

Complex x1[N] , x2[N];

void gao (int *a , int *b) {

    int len = max (n , m);

    int l = 1;

    while (l < len * 2) l <<= 1;

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

        x1[i] = Complex (a[i] , 0);

    for (int i = n ; i < l ; i ++)

        x1[i] = Complex (0 , 0);

    FFT (x1 , l , 1);

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

        x2[i] = Complex (b[i] , 0);

    for (int i = m ; i < l ; i ++)

        x2[i] = Complex (0 , 0);

    FFT (x2 , l , 1);

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

        x1[i] = x1[i] * x2[i];

    FFT (x1 , l , -1);

    for (int i = 0 ; i <= n - m ; i ++) {

        p[i] += (int)(x1[i + m - 1].a + 0.5);

    }

}

int main () {

    while (scanf ("%d %d" , &n , &m) != EOF) {

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

            scanf ("%s" , str);

            a[i] = 0;

            for (int j = 0 ; j < 7 ; j ++)

                a[i] = a[i] * 2 + str[j] - '0';

            c[i] = str[7] - '0';

        }

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

            scanf ("%s" , str);

            b[i] = 0;

            for (int j = 0 ; j < 7 ; j ++)

                b[i] = b[i] * 2 + str[j] - '0';

            d[m - i - 1] = str[7] - '0';

        }

        get_next (b , m);

        cnt = 0;

        match (a , n , b , m);

        if (cnt == 0) puts ("No");

        else {

            memset (p , 0 , sizeof(p));

            puts ("Yes");

            gao (c , d);

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

                c[i] = c[i] ^ 1;

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

                d[i] = d[i] ^ 1;

            gao (c , d);

            int ans = m + 1 , idx = -1;

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

                if (m - p[pos[i]] < ans)

                    ans = m - p[pos[i]] , idx = pos[i];

            }

            printf ("%d %d\n" , ans , idx + 1);

        }

    }

    return 0;

}