题解 P4173 【残缺的字符串】

· · 题解

题意

给一个长度为 n 的带通配符的模板串 A 和一个长度为 m 的带通配符的文本串 B，通配符可以替换任意字符，求 B 中从哪些位置开始的前缀能够匹配 A。

\texttt{Data Range:}1\leq n,m\leq 3\times 10^5

题解

这题应该不卡常的啊……

FFT 字符串匹配。

先考虑无通配符的情况。

首先需要定义一个不相似度函数 C(s,t)，代表 s 和 t 的不相似度，同时定义完全匹配函数 P(S,T) 代表 S 和 T 两个串是否完全匹配。考虑每个字符，可以得到：

P(S,T)=\sum\limits_{i=0}^{\vert S\vert}C(S_i,T_i)

不相似度函数 C(s,t) 需要满足两个性质：

第一个性质显然，考虑证明第二个性质。使用反证法，那么一定存在四个字符 a,b,c,d 满足 a\neq b,c\neq d,C(a,b)=p>0,C(c,d)=q<0，则构造如下两个字符串 S,T：S 为 -q 个 a 后面接 p 个 c，T 为 -q 个 b 后面接 p 个 d，则 P(s,t)=-q\times p+p\times q=0，然而 S 和 T 不相同，矛盾。

所以现在考虑找 C(s,t)。一个最方便的想法是设 C(s,t)=s-t（这里的减法为 ASCII 码做减法），然而并不满足性质 2，于是考虑取绝对值。绝对值没有很好的性质，所以要平方去掉，也即 C(s,t)=(s-t)^2。

这个时候考虑文本串中每一个位置与模板串的匹配情况，设 f_i 为文本串从第 i 个字符开始的完全匹配函数值，那么有（这里字符串下标从 0 开始）：

f_i=\sum\limits_{j=0}^{n}C(A_j,B_{i+j})

拆掉不相似度函数会发现这个东西是个卷积的形式，卷一下就好了。

对于通配符来讲，通配符可以跟任意字符匹配，所以设通配符的 ASCII 为 0，则可以设 C(s,t)=st(s-t)^2 即可，卷一下就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
typedef unsigned long long int ull;
const ll MAXN=1048577,MOD=998244353,G=3,INVG=332748118;
ll fd,c,r,cnt,limit;
ll rev[MAXN],omgs[MAXN],invo[MAXN],f[MAXN],g[MAXN],res[MAXN];
ll f2[MAXN],g2[MAXN],f3[MAXN],g3[MAXN];
char s[MAXN],t[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
    ll res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%MOD;
        }
        base=(li)base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void setupOmg(ll cnt)
{
    ll limit=log2(cnt)-1,omg;
    omg=qpow(G,(MOD-1)>>(limit+1)),omgs[cnt>>1]=1;
    for(register int i=(cnt>>1|1);i!=cnt;i++)
    {
        omgs[i]=(li)omgs[i-1]*omg%MOD;
    }
    for(register int i=(cnt>>1)-1;i;i--)
    {
        omgs[i]=omgs[i<<1]; 
    }
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
    static ull tcp[MAXN];
    register ll cur=0,x,shift=log2(cnt)-__builtin_ctz(cnt);
    if(inv==-1)
    {
        reverse(cp+1,cp+cnt);
    }
    for(register int i=0;i<cnt;i++)
    {
        tcp[rev[i]>>shift]=cp[i];
    }
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1;
        for(register int j=0;j<cnt;j+=i)
        {
            for(register int k=0;k<cur;k++)
            {
                x=tcp[j|k|cur]*omgs[k|cur]%MOD;
                tcp[j|k|cur]=tcp[j|k]+MOD-x,tcp[j|k]+=x;
            }
        }
    }
    for(register int i=0;i<cnt;i++)
    {
        cp[i]=tcp[i]%MOD;
    }
    if(inv==1)
    {
        return;
    }
    x=MOD-(MOD-1)/cnt;
    for(register int i=0;i<cnt;i++)
    {
        cp[i]=(li)cp[i]*x%MOD;
    }
}
int main()
{
    c=read(),fd=read(),scanf("%s%s",s,t),cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
        cnt<<=1,limit++;
    }
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    for(register int i=0;i<c;i++)
    {
        f[i]=isalpha(s[i])?s[i]-96:0;
        f2[i]=(li)f[i]*f[i],f3[i]=(li)f2[i]*f[i];
    }
    for(register int i=0;i<fd;i++)
    {
        g[i]=isalpha(t[fd-1-i])?t[fd-1-i]-96:0;
        g2[i]=(li)g[i]*g[i],g3[i]=(li)g2[i]*g[i];
    }
    setupOmg(cnt),NTT(f,cnt,1),NTT(g,cnt,1);
    NTT(f2,cnt,1),NTT(g2,cnt,1),NTT(f3,cnt,1),NTT(g3,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=((li)f3[i]*g[i]+(li)f[i]*g3[i])%MOD;
        res[i]=(res[i]-(li)2*f2[i]*g2[i]%MOD+MOD)%MOD;
    }
    NTT(res,cnt,-1),reverse(res,res+fd);
    for(register int i=0;i<fd-c+1;i++)
    {
        r+=!res[i];
    }
    printf("%d\n",r);
    for(register int i=0;i<fd-c+1;i++)
    {
        !res[i]?printf("%d ",i+1):1;
    }
}