YZOJ P3069 字符串匹配

时间限制：4000MS      内存限制：262144KB

难度：\(7.0\)

• 题目描述

给出两个串 \(A\) 和 \(B\)，串中仅包含小写字母和字符 *，其中 * 能匹配任意的小写字母（也可以匹配 *）。

请你求出如果以 \(A\) 为模板串，那么有哪些 \(i\) 使得 \(B[i,i+\left|A\right|)\) 可以与  \(A\) 匹配？

• 输入格式

第一行 \(A\)，第二行 \(B\) 。

• 输出格式

按照从小到大输出所有 \(i\) 。

• 样例输入

• 样例输出

• 数据规模与约定

对于所有数据，\(\left|A\right|, \left|B\right| \leq 500000\) 。

 

 

 

---

 

 

 

想法完全偏离正解www

设 * 为 \(0\) ，其余字母的值都与 ASCII 相对应。

构造 Hash \(\sum\limits_{i=0}^{n-1}(A_i-B_i)^2A_iB_i\) ，当且仅当它的值为 \(0\) 时 两字符串完全匹配，因为只有每一位都相等时 它的值才可能为 \(0\) 。（为了消去负数的影响所以有一个平方，考虑到 * 所以再乘上其本身。）

所以可以枚举 \(A\) 在 \(B\) 中的末尾位置 \(i\) ，当这个字串匹配时，有 \(\sum\limits_{j=0}^{m-1}(A_j-B_{i-m+1+j})^2A_jB_{i-m+1+j}=0\) 。

若把 \(A\) 串翻转，同时后面补 \(0\) 至与 \(B\) 串等长，就会有 \(\sum\limits_{j=0}^i(A_j-B_{i-j})^2A_jB_{i-j}=0\) 。

展开，有 \(\sum\limits_{j=0}^iA_{j}^3B_{i-j}-2\sum\limits_{j=0}^iA_j^2B_{i-j}^2+\sum\limits_{j=0}^iA_{j}B_{i-j}^3\) 。

跑三次 FFT 即可。