题目大意：给你两个$01$串$a$和$b$，每$8$个字符为$1$组，每组的最后一个字符可以在$01$之间转换，求$b$成为$a$的一个子串所需的最少转换次数，以及此时是从哪开始匹配的。
FFT怎么变成字符串算法了
每组的前$7$个字符是不能动的，所以把它压成一个数，用$kmp$求出$b$可能作为$a$子串的所有结束位置
求最少的转换次数呢，把$a,b$串每一组的最后一位取出来分别组成新串，再把$b$的新串反转求卷积即可
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #define N1 (1<<19)
6 #define M1 (N1<<1)
7 #define il inline
8 #define dd double
9 #define ld long double
10 #define ll long long
11 using namespace std;
12
13 int gint()
14 {
15 int ret=0,fh=1;char c=getchar();
16 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
17 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
18 return ret*fh;
19 }
20
21 const int inf=0x3f3f3f3f;
22 namespace FFT{
23
24 const dd pi=acos(-1);
25 struct cp{
26 dd x,y;
27 friend cp operator + (const cp &s1,const cp &s2){ return (cp){s1.x+s2.x,s1.y+s2.y}; }
28 friend cp operator - (const cp &s1,const cp &s2){ return (cp){s1.x-s2.x,s1.y-s2.y}; }
29 friend cp operator * (const cp &s1,const cp &s2){ return (cp){s1.x*s2.x-s1.y*s2.y,s1.y*s2.x+s1.x*s2.y}; }
30 }a[N1],b[N1],c[N1];
31 int r[N1];
32 void FFT(cp *s,int len,int type)
33 {
34 int i,j,k; cp wn,w,t;
35 for(i=0;i<len;i++) if(i<r[i]) swap(s[i],s[r[i]]);
36 for(k=2;k<=len;k<<=1)
37 {
38 wn=(cp){cos(2.0*type*pi/k),sin(2.0*type*pi/k)};
39 for(i=0;i<len;i+=k)
40 {
41 w=(cp){1,0};
42 for(j=0;j<(k>>1);j++,w=w*wn)
43 {
44 t=w*s[i+j+(k>>1)];
45 s[i+j+(k>>1)]=s[i+j]-t;
46 s[i+j]=s[i+j]+t;
47 }
48 }
49 }
50 }
51 void FFT_Main(int len)
52 {
53 int i;
54 FFT(a,len,1); FFT(b,len,1);
55 for(i=0;i<len;i++) c[i]=a[i]*b[i];
56 FFT(c,len,-1);
57 for(i=0;i<len;i++) c[i].x/=len;
58 }
59 void init()
60 {
61 memset(a,0,sizeof(a));
62 memset(b,0,sizeof(b));
63 }
64
65 };
66
67 int a[N1],b[N1],A[N1],B[N1],nxt[N1],ans[N1],num[N1];
68 void get_nxt(int len)
69 {
70 int i=0,j=-1; nxt[0]=-1;
71 while(i<len)
72 {
73 if(j==-1||b[i]==b[j]){ i++; j++; nxt[i]=j; }
74 else { j=nxt[j]; }
75 }
76 }
77 void KMP(int len)
78 {
79 int i=0,j=0;
80 while(i<len)
81 {
82 if(j==-1||a[i]==b[j]){ i++; j++; ans[i]=j; }
83 else{ j=nxt[j]; }
84 }
85 }
86
87 int T,n,m;
88
89
90 int main()
91 {
92
93 scanf("%d%d",&n,&m);
94 int i,j,s,ret=inf,id,len,L; char str[10];
95 memset(a,-1,sizeof(a)); memset(b,-1,sizeof(b));
96 for(i=0;i<n;i++)
97 {
98 scanf("%s",str);
99 for(j=0,s=0;j<7;j++) s=(s<<1)+str[j]-'0';
100 a[i]=s; A[i]=str[7]-'0';
101 }
102 for(i=0;i<m;i++)
103 {
104 scanf("%s",str);
105 for(j=0,s=0;j<7;j++) s=(s<<1)+str[j]-'0';
106 b[i]=s; B[m-i-1]=str[7]-'0';
107 }
108 for(len=1,L=0;len<n+m-1;len<<=1,L++);
109 for(i=0;i<len;i++) FFT::r[i]=(FFT::r[i>>1]>>1)|((i&1)<<(L-1));
110
111 for(i=0;i<n;i++) FFT::a[i].x=(A[i]==0)?1:0;
112 for(i=0;i<m;i++) FFT::b[i].x=(B[i]==0)?1:0;
113 FFT::FFT_Main(len);
114 for(i=0;i<len;i++) num[i]+=(int)(FFT::c[i].x+0.1);
115
116 FFT::init();
117 for(i=0;i<n;i++) FFT::a[i].x=(A[i]==1)?1:0;
118 for(i=0;i<m;i++) FFT::b[i].x=(B[i]==1)?1:0;
119 FFT::FFT_Main(len);
120 for(i=0;i<len;i++) num[i]+=(int)(FFT::c[i].x+0.1);
121
122 get_nxt(m); KMP(n);
123 for(i=m;i<=n;i++)
124 {
125 if(ans[i]<m) continue;
126 if(m-num[i-1]<ret){ id=i-m+1; ret=m-num[i-1]; }
127 }
128 if(ret==inf) puts("No");
129 else{ puts("Yes"); printf("%d %d\n",ret,id); }
130
131 return 0;
132
133 }