红酒 公司 网站建设,青岛安装建设股份公司网站,宝山顺德网站建设,网站导航建设注意事项传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; n,m,k≤2e5n,m,k\le2e5n,m,k≤2e5
思路#xff1a;
直接考虑fftfftfft来匹配字符串。 由于kkk是给定的#xff0c;所以难度低了很多#xff0c;普通的字符串匹配不能处理这种可以范围相等的情况#xf…传送门
文章目录题意思路题意 n,m,k≤2e5n,m,k\le2e5n,m,k≤2e5
思路
直接考虑fftfftfft来匹配字符串。 由于kkk是给定的所以难度低了很多普通的字符串匹配不能处理这种可以范围相等的情况看到字符集出奇的小考虑将其拆开来看。 单独看某个字符的时候考虑将字符串转换成010101串进行匹配。转换的时候只需要将当前字符的周围kkk个字符都变成当前字符即可让后之前将bbb翻转一下就可以直接卷了原理与之前写的博客相同。
// Problem: CF528D Fuzzy Search
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF528D
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6,PIacos(-1);int n,m,k;
char aa[N],bb[N];
int pre[N][26],f[N];
int A[N],B[N];
string s;
int rev[N];
int bit,limit;struct Complex {double x,y;Complex operator (const Complex t) const { return {xt.x,yt.y}; }Complex operator - (const Complex t) const { return {x-t.x,y-t.y}; }Complex operator * (const Complex t) const { return {x*t.x-y*t.y,x*t.yy*t.x}; }
}a[N],b[N];void fft(Complex a[],int inv) {for(int i0;ilimit;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int mid1;midlimit;mid1) {Complex w1Complex({cos(PI/mid),inv*sin(PI/mid)});for(int i0;ilimit;imid*2) {Complex wkComplex({1,0});for(int j0;jmid;j,wkwk*w1) {Complex xa[ij],ywk*a[ijmid];a[ij]xy; a[ijmid]x-y;}}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);sATGC;cinnmkaabb;for(int i0;in;i) {for(int j0;j4;j) pre[i][j]pre[max(i-1,0)][j](aa[i]s[j]);}while((1bit)nm) bit;limit1bit;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(bit-1));reverse(bb,bbm);for(int i0;i4;i) {char chs[i];for(int j0;jm;j) B[j]bb[j]ch;for(int j0;jn;j) {A[j]0;int lmax(0,j-k),rmin(n-1,jk);int cntpre[r][i]-(l-10? pre[l-1][i]:0);if(aa[j]ch) cnt1;if(cnt0) A[j]1;}for(int i0;ilimit;i) a[i]b[i]{0,0};for(int i0;in;i) a[i]{1.0*A[i],0};for(int i0;im;i) b[i]{1.0*B[i],0};fft(a,1); fft(b,1);for(int i0;ilimit;i) a[i]a[i]*b[i];fft(a,-1);for(int im-1;in;i) {int now(int)(a[i].x/limit0.5);f[i-m1]now;}}int ans0;for(int i0;in;i) {if(f[i]m) ans;}printf(%d\n,ans);return 0;
}
/**/
