我得到一个字符串，它只包含从0到9的数字。我想计算它们有多少子串是2的幂。
例如，对于子串2560616，子串256和16是2的幂。我需要计算在任何给定的子串中有多少这样的子串。
请注意，子字符串非常大，因此蛮力无法工作。所以我主要想解决两个问题
如何有效地计算2次方的所有子串
如何有效计算子串是否为2的幂
我想可能有一个DP方法，但我不确定。
最佳答案
使用以下算法从2的幂位数创建树：
从表示空字符的根开始。
得到下一个2的幂，按相反的顺序得到它的数字。
选择根。选择当前号码的最后一位。
转到与所选数字对应的所选节点的子节点。如果它还不存在，创造它。
选择当前号码的前一位。从（2.）开始重复，直到不再有数字为止。
将当前节点标记为有效的终结点。
从（2.）重复到位数>10^5
这棵树可能会占用内存几GB。
现在你有了你的树。要计算2次方的子字符串数，请执行以下操作：
从字符串的末尾开始。
获取上一个字符。
选择树根。
选择上一个字符（从外部选定的字符开始（2.））。
选择与所选数字对应的所选节点的子节点。
如果选定的子节点标记为有效的终结点，则将计数增加1。
从（2.）重复，直到所选节点为空或达到字符串的第一个字符。
返回到外部选定的角色（2.）
选择上一个字符。从（2.）开始重复，直到到达字符串的开头。
对算法的描述并不是“考试就绪”，但我希望它足够容易理解。