P6739 [BalticOI 2014 Day1] Three Friends 题解

目录

• 写在前面
• Solution
  • 何为字符串哈希（可跳过）：
• Code

写在前面

P6739 [BalticOI 2014 Day1] Three Friends

听说这题可以用比较暴力的做法过，比如 \(string\) 里面自带的 \(substr\) ，可以看这位大佬的提交记录

模数不要用 \(49999\) ，会被卡， \(1e9+9\) 才是真爱

Solution

何为字符串哈希（可跳过）：

由于字符串是具有前后关系的，可以按下述方法构造：
选取两个合适的互质常数 \(b\) 和 \(h (b < h)\)， 假设有一个字符串 \(C = c_1c_2···c_m\)，那么我们定义哈希函数：

\[H(C) = (c_1b^{m - 1} + c_2b^{m - 2} + ···+c_mb^{0}) \mod h \]

考虑递推实现，设 \(H(C, k)\) 为前 \(k\) 个字符构成的字符串的哈希值，则：

\[H(C, k + 1) = H(C, k) \times b + c_{k + 1} \]

通常，题目要求的是判断主串的一段字符与另一个匹配串是否匹配，即判断字符串 \(C = c_1c_2···c_m\) 从位置 \(k + 1\) 开始的长度为 \(n\) 的子串 \(C^{'} = c_{k + 1}c_{k + 2}···c_{k + n}\) 的哈希值与另一匹配串 \(S = s_1s_2···s_n\) 的哈希值是否相等，则：

\[H(C_{'}) = H(C, k + n) - H(C, k) \times b^{n} \]

只要预求得 \(b^{n}\) ，就能 \(O(1)\) 判断了

可以预处理出所有 \(b^{n}\) 存在 \(Pow\) 数组里

---

观察目标串 \(U\) 的构造方式，发现如果 \(N\) 是偶数，一定无法构造

然后考虑枚举删除每一个字符，再将剩下的字符串均分判断哈希值是否相等

假设删去的字符在前半段，那么后半段的一定是原字符串 \(S\)，如果在后半段，那么前半段一定是原字符串 \(S\) ，

所以可以分开枚举，并且预处理出对应的原字符串

那么删掉一个字符后，剩下的两段怎么合并呢？以样例字符串为例：

\[ABXCABC \]

假设枚举到 \(X\)

那么原字符串为 \(ABC\)，前面要合并的两段字符串是 \(AB\)，\(C\)

如果朴素计算这两个串的哈希值及原字符串哈希值，计算过程如下：

\[AB = A * b^{1} + B * b^{0} \]

\[C = C * b^{0} \]

\[ABC = A * b^{2} + B * b^{1} + C * b^{0} \]

所以不难看出 \(ABC = AB * b^{1} + C\)

对这个结论进行推广，对于字符串 \(X\)，删掉其中一个字符后，分成两个字符串\(X_1,X_2\)，有

\[X = X_1 * b^{len_{X_2}} + X_2 \]

根据这个公式去进行合并，然后比较两个字符串哈希值是否相同

然后这就可以了吗？ 不不不

看这个样例

13
AABCABCABCABC

我们会发现删掉第一个和第二个字符都可以，但得到的原串都是 \(ABCABC\)

所以注意开个map判重即可

如果还A不了，兄弟，改个模数试试吧

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#include