题意

给出\(n\)个01字节和\(m\)个01字节，要求用后者去匹配前者，两个串能匹配当且仅当除了每个字节末位不同，其他位都要相同。问匹配后者至少有多少个末位不同。（\(1 \le m \le n \le 2.5 \times 10^5\)）

分析

首先我们可以用kmp计算出能匹配的位置，然后单独考虑末位不同的情况。

题解

我们将末尾的位提取出来，则考虑\(n\)个\(01\)位和\(m\)个\(01\)位。对于模板串的\(01\)位，我们需要计算以这个位置结束与匹配串位相同的数目，发现其实我们将匹配串反转，然后就是卷积！于是我们就可以用fft做了。

#include <bits/stdc++.h>

using namespace std;

const double pi=acos(-1);

const int N=2.5e5+10, nS=N*8, Lim=600006;

int lenn, lenm, lena, lenb, got[Lim], rev[Lim];

char s1[nS], s2[nS], sa[nS], sb[nS];

vector<int> pos;

void getkmp() {

	static int p[nS];

	memset(p, -1, sizeof(int)*lena);

	int j=-1;

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

		while(j!=-1 && sa[j+1]!=sa[i]) j=p[j];

		if(sa[j+1]==sa[i]) ++j;

		p[i]=j;

	}

	j=-1;

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

		while(j!=-1 && sb[j+1]!=sa[i]) j=p[j];

		if(sb[j+1]==sa[i]) ++j;

		if(j==lenb-1) {

			int t=i-j;

			if(t%7==0) {

				pos.push_back(t/7);

			}

		}

	}

}

struct icp {

	double r, i;

	icp(double _r=0, double _i=0) : r(_r), i(_i) { }

};

icp operator + (const icp &a, const icp &b) { return icp(a.r+b.r, a.i+b.i); }

icp operator - (const icp &a, const icp &b) { return icp(a.r-b.r, a.i-b.i); }

icp operator * (const icp &a, const icp &b) { return icp(a.r*b.r-a.i*b.i, a.r*b.i+a.i*b.r); }

int getlen(int n) {

	int len=1, bl=-1;

	for(; len<n; len<<=1, ++bl);

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

		rev[i]=(rev[i>>1]>>1)|((i&1)<<bl);

	}

	return len;

}

void fft(icp *a, int n, int flag) {

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

		if(rev[i]<i) {

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

		}

	}

	for(int m=2; m<=n; m<<=1) {

		icp wn(cos(pi*2/m), sin(pi*2/m)*flag);

		for(int i=0, mid=m>>1; i<n; i+=m) {

			icp w(1);

			for(int j=0; j<mid; ++j) {

				icp u=a[i+j], v=a[i+j+mid]*w;

				a[i+j]=u+v;

				a[i+j+mid]=u-v;

				w=w*wn;

			}

		}

	}

	if(flag==-1) {

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

			a[i].r/=n;

		}

	}

}

void dofft(char *A, char *B, int *C, int n, int m) {

#define CLR(a) for(int i=0; i<len; ++i) a[i].r=a[i].i=0;

	static icp a[Lim], b[Lim], c[Lim];

	int len=getlen(n+m-1);

	CLR(a);

	CLR(b);

	CLR(c);

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

		a[i].r=A[i]-'0';

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

		b[i].r=B[i]-'0';

	fft(a, len, 1);

	fft(b, len, 1);

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

		c[i]=a[i]*b[i];

	fft(c, len, -1);

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

		C[i]+=c[i].r+0.5;

}

void getfft() {

	lena=lenb=0;

	for(int i=7; i<lenn; i+=8)

		sa[lena++]=s1[i];

	for(int i=lenm-1; i>=0; i-=8)

		sb[lenb++]=s2[i];

	dofft(sa, sb, got, lena, lenb);

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

		sa[i]=sa[i]=='0'?'1':'0';

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

		sb[i]=sb[i]=='0'?'1':'0';

	dofft(sa, sb, got, lena, lenb);

}

int main() {

	int n, m;

	scanf("%d%d", &n, &m);

	lenn=n*8, lenm=m*8;

	char *it;

	it=s1;

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

		scanf("%s", it);

		for(; *it; ++it) {

			if(*(it+1)) {

				sa[lena++]=*it;

			}

		}

	}

	it=s2;

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

		scanf("%s", it);

		for(; *it; ++it) {

			if(*(it+1)) {

				sb[lenb++]=*it;

			}

		}

	}

	getkmp();

	getfft();

	if(!pos.size()) {

		puts("No");

		return 0;

	}

	int ans1=n, ans2=~0u>>1;

	for(int i=0, len=pos.size(); i<len; ++i) {

		int p=pos[i], t=(m-got[p+m-1]);

		if(ans2==t) {

			ans1=min(p, ans1);

		}

		else if(ans2>t) {

			ans2=t;

			ans1=p;

		}

	}

	printf("Yes\n%d %d\n", ans2, ans1+1);

	return 0;

}