luogu P4173 残缺的字符串

嘟嘟嘟


如题，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;   
}