luogu P4173 残缺的字符串

概述嘟嘟嘟 如题，FFT残缺字符串匹配。 简单来说，就是定义一个匹配函数，然后稍稍推一下柿子。 细节来不及写了，推荐luogu的第一篇题解，讲的特别好。 （没事别开long double，这东西慢的很） #include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<c

嘟嘟嘟


如题，FFT残缺字符串匹配。


简单来说，就是定义一个匹配函数，然后稍稍推一下柿子。
细节来不及写了，推荐luogu的第一篇题解，讲的特别好。
（没事别开long double，这东西慢的很）

#include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<cstdlib>#include<cctype>#include<vector>#include<queue>#include<assert.h>#include<ctime>using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a,x) memset(a,x,sizeof(a))#define In inline#define forE(i,y) for(int i = head[x],y; ~i && (y = e[i].to); i = e[i].nxt)typedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 3e5 + 5;const int maxN = 1.1e6 + 5;const db PI = acos(-1);inline ll read(){    ll ans = 0;    char ch = getchar(),last = ' ';    while(!isdigit(ch)) last = ch,ch = getchar();    while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0',ch = getchar();    if(last == '-') ans = -ans;    return ans;}inline voID write(ll x){    if(x < 0) x = -x,putchar('-');    if(x >= 10) write(x / 10);    putchar(x % 10 + '0');}In voID MYfile(){#ifndef mrclr    freopen("ha.in","r",stdin);    freopen("ha.out","w",stdout);#endif}int n,m;char a1[maxn],b1[maxn];int len = 1,lim = 0,rev[maxN];struct Comp{    db x,y;    In Comp operator + (const Comp& oth)const    {        return (Comp){x + oth.x,y + oth.y};    }    In Comp operator - (const Comp& oth)const    {        return (Comp){x - oth.x,y - oth.y};    }    In Comp operator * (const Comp& oth)const    {        return (Comp){x * oth.x - y * oth.y,x * oth.y + y * oth.x};    }    frIEnd In voID swap(Comp& A,Comp& B)    {        swap(A.x,B.x),swap(A.y,B.y);    }}A[maxN],B[maxN],ans[maxN];In voID fft(ComP* a,int len,int flg){    for(int i = 0; i < len; ++i) if(i < rev[i]) swap(a[i],a[rev[i]]);    for(int i = 1; i < len; i <<= 1)    {        Comp omg = (Comp){cos(PI / i),sin(PI / i) * flg};        for(int j = 0; j < len; j += (i << 1))        {            Comp o = (Comp){1,0};            for(int k = 0; k < i; ++k,o = o * omg)            {                Comp tp1 = a[j + k],tp2 = a[j + k + i] * o;                a[j + k] = tp1 + tp2,a[j + k + i] = tp1 - tp2;            }        }    }}int a[maxn],b[maxn];In voID fftmatch(){    reverse(a1,a1 + m);    for(int i = 0; i < m; ++i) a[i] = a1[i] == '*' ? 0 : a1[i] - 'a' + 1;    for(int i = 0; i < n; ++i) b[i] = b1[i] == '*' ? 0 : b1[i] - 'a' + 1;    while(len < n + n) len <<= 1,++lim;    for(int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));    for(int i = 0; i < len; ++i)    {        A[i] = (Comp){i < m ? a[i] * a[i] * a[i] : 0,0};        B[i] = (Comp){i < n ? b[i] : 0,0};    }    fft(A,len,1),fft(B,1);    for(int i = 0; i < len; ++i) ans[i] = ans[i] + A[i] * B[i];    for(int i = 0 ; i < len; ++i)    {        A[i] = (Comp){i < m ? a[i] * a[i] : 0,0};        B[i] = (Comp){i < n ? b[i] * b[i] : 0,0};      }    fft(A,1);    for(int i = 0; i < len; ++i) ans[i] = ans[i] - A[i] * B[i] * (Comp){2,0};    for(int i = 0; i < len; ++i)    {        A[i] = (Comp){i < m ? a[i] : 0,0};        B[i] = (Comp){i < n ? b[i] * b[i] * b[i]: 0,1);    for(int i = 0; i < len; ++i) ans[i] = ans[i] + A[i] * B[i];    fft(ans,-1);}int Ans[maxn],tot = 0;int main(){//  MYfile();    m = read(),n = read();    scanf("%s%s",a1,b1);    fftmatch();    for(int i = m - 1; i < n; ++i)         if(!((ll)(ans[i].x / len + 0.5))) Ans[++tot] = i - m + 2;    write(tot),enter;    if(tot) {for(int i = 1; i <= tot; ++i) write(Ans[i]),space; enter;}    return 0;   }

总结

以上是内存溢出为你收集整理的luogu P4173 残缺的字符串全部内容，希望文章能够帮你解决luogu P4173 残缺的字符串所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。