java - 给定一个数字检查数字是否形成加法方程？

Question

给定一个字符串S，我想找出是否存在不重叠的子串A、B和C 在 S 中，因此当子字符串被解释为十进制数时，等式 A + B = C 成立。

示例:对于 S = 17512，答案是肯定的，因为 12 + 5 = 17 成立。

这不是作业题，我已经尝试过构建后缀数组来解决这个问题

17512

7512

512

12

2

但后来我意识到给定 132，1 + 2 = 3在选择时是否需要其他形式的排列？

如何有效地解决这个问题？

Answer 1

令 S 为数字的十进制表示。如果 n = |S| 足够小(<500 左右)，您可以使用以下算法:

让我们从等式 A + B = C 中枚举 A 和 C(我们假设 w.l.o.g. A > B)。我们知道它们的大小必须大致相同(加/减一位数)，因此枚举可能性是一次三次运算(有 O(n³)候选人)。

对于每个候选对 (A, C)，我们需要检查 B = C - A 是否在字符串中并且不与任何 重叠>A 或 C 子串。我们可以使用以 10 为基数的算术计算线性时间的差异。

棘手的部分是检查B 是否是不与A 或C 重叠的子串。 A 和 C 将字符串分成 3 部分:

S = xAyCz

如果我们以一种巧妙的方式枚举它们，固定起始位置并减小大小，我们可以维护 suffix automata部分 x 和部分 y 和 z 的反面。

现在我们可以在线性时间内检查 B = C - A(或其相反)是否存在于这三个部分之一中。

这种方法的时间复杂度:Θ(n⁴)。

这里有一个变体，稍微复杂一些，但速度更快(感谢 Evgeny 指出):

• 创建输入字符串的后缀树。每个节点代表一个子串。在每个节点中存储子字符串在字符串中出现的位置的平衡二叉搜索树。此处您可能需要持久树以节省时间和空间。
• 枚举 A 和 C，但这次从最低有效数字(最右端)开始。
• 在从右到左增加 A 和 C 的同时，跟踪 B = C - A 的结果。它也会从最低位增长到最高位。在后缀树中搜索 B。您可以一次执行一位数，因此您可以使 A 和 C 增长一位数，更新 B 并将其定位在 O(1) 的后缀树中。
• 如果B为正，则在位置的BBST中做三个范围查询，检查B是否出现在字符串中，且不与A或C重叠

运行时间:O(n³ log n)。

更新:关于需要使用所有字符的简化版本:

我们首先意识到，如果我们以 10 为基数，我们可以在线性时间内对字符串的子串进行算术运算。

现在我们要找到 split 点a < b，这样你的三个子串就是A = s₁...s_a ，B = s_a+1...s_b 和C = s_b+1...s_n.

我们可以证明a 和b 的候选数只有常数，因为这三个部分的大小必须大致相同，方程才能成立。

使用任意精度算法，我们可以轻松地尝试所有候选对 (a,b) 并针对每个候选对找到 M = max(A,B,C)。然后检查 M 是否是其他两个数字的总和。

总时间复杂度:Θ(n)。