string - 查找具有特定属性的数字子串

Question

我得到一个仅由 0 到 9 之间的数字组成的字符串。我想计算其中有多少个子字符串是 2 的幂。

例如对于子字符串 2560616，子字符串 256 和 16 是 2 的幂。我需要计算在任何给定的子字符串中有多少个这样的子字符串。

请注意，子字符串非常大，因此暴力破解是行不通的。所以我主要想解决2个问题

1. 如何有效地计算所有 2 的幂子串
2. 如何高效计算子串是否为2的幂

我认为可能有 DP 方法，但我不确定。

Answer 1

使用以下算法从 2 的幂的数字创建一棵树:

1. 以代表空字符的词根开始。
2. 求出 2 的下一次幂，逆序求出它的数字。
   1. 选择根。选择当前号码的最后一位。
   2. 转到所选数字对应的所选节点的子节点。如果尚不存在，请创建它。
   3. 选择当前号码的前一位。从 (2.) 开始重复，直到没有更多数字。
   4. 将当前节点标记为有效端点。
3. 从 (2.) 开始重复，直到位数 > 10^5

这棵树可能需要几 GB 的内存。

现在你有了你的树。要计算 2 的幂的子字符串数，请执行以下操作:

1. 从字符串末尾开始。
2. 获取前一个字符。
   1. 选择树的根。
   2. 选择前一个字符(从在外部 (2.) 中选择的字符开始)。
   3. 选择所选数字对应的所选节点的子节点。
   4. 如果选定的子节点被标记为有效端点，则将计数递增 1。
   5. 从 (2.) 开始重复，直到所选节点为空或到达字符串的第一个字符。
   6. 返回到在外部 (2.) 中选择的字符
3. 选择上一个字符。从 (2.) 开始重复，直到到达字符串的开头。

算法的描述不是“考试准备”，但我希望它足够容易理解。