题意
给\(N,M(N,M \le 250000)\)的两个由8位二进制表示的两个序列，允许改变每个数字的第8位的数值（即0→1，1→0），求改变最少次数使得长为\(M\)的序列为长为\(N\)的连续子序列，在次数最少的前提下，找到下标最小的起始位置。
思路
- 因为只能改变第8位的状态，所以若能匹配的话，前7位数值需要相同，这步通过KMP完成即可。
- 剩下就是如何快速求每个匹配区间所需要的代价，即找出两个长为\(M\)的序列对应位不同的个数。
- 考虑位置\(A[i, i + M - 1]\)，若按\(0.. M-1\)对应匹配显然没什么规律，而如果按\(M-1..0\)，则匹配位置的下标和均为\(i+M-1\)，将0和1分开作，用FFT完成计数即可。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<assert.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define setIO(x) freopen(x".in","r", stdin);freopen(x".out","w",stdout);
typedef long long ll;
typedef pair<int, int> pii;
const ll LINF = 1e10 + 7;
const int N = 3e5 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-8;
//-----------------head-----------------
struct C {
double r, i;
C() {
r = i = 0;
}
C(double _r, double _i) {
r = _r, i = _i;
}
C operator+(const C &p) const {
return C(r + p.r, i + p.i);
}
C operator-(const C &p) const {
return C(r - p.r, i - p.i);
}
C operator*(const C &p) const {
return C(r * p.r - i * p.i, r * p.i + i * p.r);
}
} A[N * 2], B[N * 2];
int n, m, a[N], b[N], p[N], s[2][N];
void fft(C x[], int n, int rev) {
int i, j, k, t;
for (i = 1; i < n; ++i) {
for (j = 0, k = n >> 1, t = i; k; k >>= 1, t >>= 1)
j = j << 1 | (t & 1);
if (i < j)
swap(x[i], x[j]);
}
for (int s = 2, ds = 1; s <= n; ds = s, s <<= 1) {
C w = C(1, 0), t;
C wn = C(cos(2.0 * rev * PI / s), sin(2.0 * rev * PI / s));
for (k = 0; k < ds; ++k, w = w * wn)
for (i = k; i < n; i += s) {
t = w * x[i + ds];
x[i + ds] = x[i] - t;
x[i] = x[i] + t;
}
}
if (rev == -1)
for (i = 0; i < n; ++i)
x[i].r /= n;
}
int read() {
int x = 0;
char ch = getchar();
while (ch != '0' && ch != '1')
ch = getchar();
while (ch == '0' || ch == '1') {
x = (x << 1) | (ch - '0');
ch = getchar();
}
return x;
}
void solve() {
int L = 1;
while (L < n + m)
L <<= 1;
rep(w, 0, 2)
{
rep(i, 0, n)
A[i] = C((a[i] & 1) == w, 0);
rep(i, n, L)
A[i] = C(0, 0);
rep(i, 0, m)
B[m - i - 1] = C((b[i] & 1) == w, 0);
rep(i, m, L)
B[i] = C(0, 0);
fft(A, L, 1), fft(B, L, 1);
rep(i, 0, L)
A[i] = A[i] * B[i];
fft(A, L, -1);
rep(i, 0, n)
s[w][i] = A[i].r + EPS;
}
rep(i, 0, n)
a[i] >>= 1;
rep(i, 0, m)
b[i] >>= 1;
p[0] = -1;
for (int i = 1, j = -1; i < m; ++i) {
while (j >= 0 && b[j + 1] != b[i])
j = p[j];
j += b[j + 1] == b[i];
p[i] = j;
}
pii ans = mp(INF, INF);
for (int i = 0, j = -1; i < n; ++i) {
while (j >= 0 && b[j + 1] != a[i])
j = p[j];
j += b[j + 1] == a[i];
if (j == m - 1) {
pii tmp = mp(m - s[0][i] - s[1][i], i - m + 2);
ans = min(ans, tmp);
j = p[j];
}
}
if (ans.first < INF) {
puts("Yes");
printf("%d %d\n", ans.first, ans.second);
} else {
puts("No");
}
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 0, n)
a[i] = read();
rep(i, 0, m)
b[i] = read();
solve();
return 0;
}