YZOJ P3069 字符串匹配

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 即可。

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注