URAL - 1996
题意：
URAL - 1996 给两个长度分别为$n, m$的字节串$A,B$，$A$串的最后一位可以修改，代价为$1$，求使得$B$串为$A$串字串的最小代价
Solution :
因为$A$串只有最后最后一位可以修改，所以可以用KMP求出可能匹配的位置，然后计算每个位置的$cost$
记$A$串最后一位构成的串为$a$， $B$串的为$b$, 假设$pos(0\le pos \le n-m)是可能匹配的位置$，如果将$b$反转得到$b’$, 在此处的的代价为
$$ \sum_{i+j=pos+m-1} [a_i \ne b’_j ] $$
而
$$ \sum_{i+j=posm-1} a_j * b’_j $$
可以算出来相等的$1$的个数$cnt_1$，再将$a,b$串取反，再做一次卷积就可以算出$0$相等的个数$cnt_2$，$ans=m-cnt_1-cnt_2$
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <unordered_map>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
#define debug(x) cout << #x << " " << x << "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
#ifdef DEBUG
const int MAX = 2e3 + 50;
#else
const int MAX = 1e6 + 50;
#endif
const int mod = 1e9 + 7;
#include <complex>
namespace FFT
{
int rev[MAX];
int cnt[MAX];
void fft(complex<double> *a, int n, int inv){
int bit = 0;
while((1 << bit) < n) bit++;
for(int i = 0; i < n; i++){
rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1));
if(i < rev[i])
swap(a[i], a[rev[i]]);
}
for(int mid = 1; mid < n; mid <<= 1){
complex<double> wn(cos(PI/mid), inv*sin(PI/mid));
for(int i = 0; i < n; i += (mid<<1)){
complex<double> w(1, 0);
for(int j = 0; j < mid; j++, w *= wn){
complex<double> u = a[i+j], t = w * a[i+j+mid];
a[i+j] = u+t, a[i+j+mid] = u-t;
}
}
}
}
void work(complex<double> *ss, complex<double> *rev_t, int N, int n, int m){
FFT::fft(ss, N, 1);
FFT::fft(rev_t, N, 1);
for(int i = 0; i <= N; i++) {
ss[i] *= rev_t[i];
}
FFT::fft(ss, N, -1);
for(int i = 0; i <= n-m; i++){
cnt[i] += (int)(ss[i+m-1].real() / N + 0.5);
}
}
};
complex<double> a[MAX],b[MAX];
int x[MAX], y[MAX];
int s[MAX], t[MAX];
complex<double> ss[MAX], rev_t[MAX];
char ch[10];
void input(int *x, int *s, int n){
for(int i = 0; i < n; i++){
scanf("%s", ch);
for(int j = 0; j < 6; j++) if(ch[j] == '1')
x[i] += 1 << j;
s[i] = (ch[7] == '1');
}
}
struct KMP
{
int next[MAX];
vector<int> pos;
void init(int *x, int n){
next[0] = -1;
int k = -1;
for(int i = 1; i < n; i++){
while(k > -1 and x[k+1] != x[i])
k = next[k];
if(x[k+1] == x[i]) k++;
next[i] = k;
}
}
void work(int *x, int n, int *y, int m){
int k = -1;
init(x, n);
for(int i =0; i < m; i++){
while(k > -1 and x[k+1] != y[i])
k = next[k];
if(x[k+1] == y[i]) k++;
if(k == n-1) {
pos.push_back(i-n+1);
k = next[k];
}
}
}
}kmp;
int main(){
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
int n, m;
scanf("%d%d", &n, &m);
input(x,s,n);
input(y, t, m);
kmp.init(y, m);
kmp.work(y, m, x, n);
if(kmp.pos.empty()){
puts("No");
return 0;
}
int N = 1;
while(N <= n+m) N<<=1;
for(int i = 0; i < n; i++) ss[i] = complex<double>(s[i], 0);
for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-1-i], 0);
FFT::work(ss, rev_t, N, n, m);
for(int i = 0; i < n; i++) s[i] ^= 1;
for(int i = 0; i < m; i++) t[i] ^= 1;
for(int i = 0; i < n; i++) ss[i] = complex<double>(s[i], 0);
for(int i = n; i < N; i++) ss[i] = complex<double>(0, 0);
for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-i-1], 0);
for(int i = m; i < N; i++)
rev_t[i] = complex<double>(0, 0);
FFT::work(ss, rev_t, N, n, m);
int res = inf, id = -1;
for(int i = 0; i < kmp.pos.size(); i++){
int pos = kmp.pos[i];
// pos += m-1;
int cost = m - FFT::cnt[pos];
if(cost < res){
res = cost, id = kmp.pos[i];
}
}
puts("Yes");
printf("%d %d\n", res, id+1);
return 0;
}