2020-2021:teams:wangzai_milk:fft_的一些奇妙用法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:fft_的一些奇妙用法 [2020/08/21 13:21] wzx27 |
2020-2021:teams:wangzai_milk:fft_的一些奇妙用法 [2020/08/21 13:23] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 101: | 行 101: | ||
| 上述条件可用一个式子来表示 $\sum _{i=0}^{m-1} (s_i - t_{x-m+i+1})^2 = 0$，展开后为 $\sum _{i=0}^{m-1} s_i^2 + t_{x-m+i+1}^2 - 2\cdot s_i\cdot t_{x-m+i+1}$。 | 上述条件可用一个式子来表示 $\sum _{i=0}^{m-1} (s_i - t_{x-m+i+1})^2 = 0$，展开后为 $\sum _{i=0}^{m-1} s_i^2 + t_{x-m+i+1}^2 - 2\cdot s_i\cdot t_{x-m+i+1}$。 | ||
| - | 两个平方项都可以通过前缀和得到。乘积项转换一下就会变成一个卷积的形式：把 $s$ 串翻转一下得到 $rs$ 串，于是乘积项就是 $\sum _{i=0}^{m-1} 2\cdot rs_{m-i-1} \cdot t_{x-m+i+1} = \sum _{i=0}^{m-1} rs_i \cdot t_{x-i}$。所以这里就可以用$\text{FFT}$处理的到。 | + | 两个平方项都可以通过前缀和得到。乘积项转换一下就会变成一个卷积的形式：把 $s$ 串翻转一下得到 $rs$ 串，于是乘积项就是 $\sum _{i=0}^{m-1} 2\cdot rs_{m-i-1} \cdot t_{x-m+i+1} = \sum _{i=0}^{m-1} 2\cdot rs_i \cdot t_{x-i}$。所以这里就可以用$\text{FFT}$处理的到。 |
| - | 最后的判断条件：卷积之后的多项式为 $f(x)$，在 $t$ 串的 $x0$ 位置匹配当且仅当 $f(x) + pres[m-1] + pret[x] - pret[x-m-2] = 0$。总复杂度为 $O(nlogn)$。 | + | 最后的判断条件：卷积之后的多项式为 $f(x)$，在 $t$ 串的 $x$ 位置匹配当且仅当 $f(x) + pres[m-1] + pret[x] - pret[x-m-2] = 0$。总复杂度为 $O(nlogn)$。 |
| 虽然 $\text{FFT}$ 多了一个 $log$ 的复杂度，但有些匹配是 $\text{KMP}$ 无法做但是 $\text{FFT}$ 可以做。 | 虽然 $\text{FFT}$ 多了一个 $log$ 的复杂度，但有些匹配是 $\text{KMP}$ 无法做但是 $\text{FFT}$ 可以做。 | ||
| - | [[https://www.luogu.com.cn/problem/P4173||P4173]] | + | [[https://www.luogu.com.cn/problem/P4173|P4173]] |
| 在正常匹配的基础上扩大了字符集的范围，多了一种 $*$ 字符（可以匹配任何字符）。这样之后就不能用 $\text{KMP}$ 了，因为 $\text{KMP}$ 需要满足一种等价关系，而通配符 $*$ 的存在就不满足等价关系：$a = * 且 b = *$ 但没有传递性 $a = b$。 | 在正常匹配的基础上扩大了字符集的范围，多了一种 $*$ 字符（可以匹配任何字符）。这样之后就不能用 $\text{KMP}$ 了，因为 $\text{KMP}$ 需要满足一种等价关系，而通配符 $*$ 的存在就不满足等价关系：$a = * 且 b = *$ 但没有传递性 $a = b$。 | ||
| 行 218: | 行 218: | ||
| } | } | ||
| </code> </hidden> | </code> </hidden> | ||
| + | \\ | ||
| [[https://codeforces.com/problemset/problem/1334/G|CF1334G]] | [[https://codeforces.com/problemset/problem/1334/G|CF1334G]] | ||
| 行 340: | 行 340: | ||
| } | } | ||
| </code> </hidden> | </code> </hidden> | ||
| + | \\ | ||
2020-2021/teams/wangzai_milk/fft_的一些奇妙用法.1597987292.txt.gz · 最后更改: 2020/08/21 13:21 由 wzx27
