BZOJ 4503 兩個串

2022-09-22 19:22:28 字數 996 閱讀 3252

p.s.對於這類只有相等匹配和萬能匹配的字串問題可以一遍fft

令\(s\)為文字串,\(t\)為模式串\((m=t.size())\),然後構造

\[a[i]=s[i],b[i]=(t[i]=='?'?0:t[i])

\]\[c[i]=\sum_^(a[i+j]-b[j])^2b[j]

\]然後考慮到此時如果\(s[i->i+m]\)與\(t\)匹配當且僅當\(c[i]=0\)

那麼開始轉變成卷積形式

\[c[i]=\sum_^a[i+j]^2b[j]-2a[i+j]b[j]^2+b[j]^3

\]那麼構造三個卷積\(f,g,h\)

\[f[i]=\sum_^a[i+j]^2b[j]

\]\[=>f'[m+i-1]=\sum_^a[i+j]^2b'[m-j-1]

\]\[g[i]=\sum_^2a[i+j]b[j]^2

\]\[=>g'[m+i-1]=\sum_^2\times a[i+j]b'[m-j-1]^2

\]\[h[i]=\sum_^b[j]^3

\]

#includeusing namespace std;

namespace tzh;

} complex operator -(const complex &b) const;

} complex operator *(const complex &b) const;

} complex operator *(const dd b) const;

} }omg[maxn],s[maxn],inv[maxn],c[maxn],s2[maxn],f[maxn],g[maxn],

t[maxn],t_rev[maxn],h,t2[maxn],t2_rev[maxn];

void init()

void fft(complex *a,complex *omg)

}int main()

BZOJ 4503 兩個串

我們定義一個函式, f x y a x b y 2 b y ,使得有萬用字元的時候和相等的時候都為0 begin sum sum a b j 2b j sum sum a 2 2a b j b j 2 b j sum sum a 2b j 2a b j 2 b j 3 sum sum a 2b j s...

bzoj4503 兩個串

傳送門 題解 我們設匹配函式f a i b i 2 b i 那麼展開f,做卷積就能得出f的值了 對於t i b i 0,顯然當f 0表示匹配...