bzoj1590，Secret，Message

bzoj1590 Secret Message是一道经典的字符串算法题目，涉及字符串哈希、二分答案、前缀和等算法技巧，对于提升字符串算法的能力有很大的帮助。

题目描述

现有一长度为 $n$ 的字符串 $S$，其中有若干个长度为 $t$ 的子串，每个子串都有一个权值 $val$。现在需要将字符串 $S$ 分成若干段，每段中必须恰好包含一个权值为 $val$ 的子串，且每段的长度均不超过 $m$，求最少需要分成多少段。

解题思路

由于需要将字符串 $S$ 分成若干段，且每段中必须包含一个权值为 $val$ 的子串，因此可以考虑枚举每个权值 $val$，然后对字符串 $S$ 进行分段。

具体地，我们可以使用前缀和的思想，对字符串 $S$ 进行预处理，得到一个前缀权值和数组 $sum$，其中 $sum_i$ 表示以第 $i$ 个字符结尾的子串的权值和。此时，对于每个权值 $val$，我们需要找到字符串 $S$ 中所有权值为 $val$ 的子串的位置，以此为分割点将字符串分成若干段。

在这一过程中，由于每段的长度均不超过 $m$，因此可以使用二分答案来确定每个分割点。具体地，我们可以设当前分割点为 $p$，枚举前一个分割点 $q$，然后判断长度 $[q+1,p]$ 的子串是否可以分成以 $val$ 为权值的子串。如果可以分成，则记录当前分割点 $p$ 的答案，然后继续枚举下一个分割点。

在判断长度为 $[q+1,p]$ 的子串是否可以分成以 $val$ 为权值的子串时，我们可以使用字符串哈希来判断。具体地，我们可以使用哈希表来存储所有权值为 $val$ 的子串的起始位置，然后通过哈希值的相等性来判断一个子串是否为权值为 $val$ 的子串。在哈希表中查询一个子串的时间复杂度为 $O(1)$，因此总复杂度为 $O(nm)$。

代码实现

以下是基于C++的代码实现：