找出一个字符串中可以被数字k整除的子串的个数

Question

给定一个字符串，我想找到可以由原始字符串形成的所有子字符串，这些子字符串可以被整数 k 整除。例如字符串 14917 可以形成 7 个子字符串，这些子字符串可以被整数 7 整除。子字符串是：14、1491、14917、49、91、917 和 7。我想出了一个解决方案，但它没有输入大字符串时高效运行。我的代码是

string = '14917'
divider = 7

count = 0
for i in range(len(string)):
    for j in range(i+1, len(string)+1):
        sub_string = string[i:j]
        if int(sub_string) % divider == 0:
            count += 1

print(count) 

我已经阅读了有关此类问题的快速方法，其中大部分都谈到了计算字符串的滚动余数，但我无法真正正确地实现它。有什么办法可以快速解决这个问题。提前致谢。

Answer 1

如果我们只想要计数，这里是如何解决这个问题的概述，我们不介意有多种方法可以将相同的子串拉出，并且k相对质数10（哪个7）。

首先让我们从数字的最后一位数字到第一位数字，跟踪整个数字的余数。在这种情况下14917，意味着编制下表：

number  10**digits % 7   digit  remainder
                                          0
     7         1           7     0+1*7 -> 0
    17         3           1     0+3*1 -> 3
   917         2           9     3+2*9 -> 0
  4917         6           4     0+6*4 -> 3
 14917         4           1     3+4*1 -> 0

现在这是诀窍。每当你在两个地方看到相同的余数，那么从一个到另一个你就得到了可以被 7 整除的东西。因此，例如，在两个 3 之间你得到 49。如果一个特定的值出现i次数，那么这代表i*(i-1)/2（可能相同）可以被 7 整除的子串。

如果我们想获得独特的子串，然后我们做了很多更多的工作。但是O(length of string)如果我们生成一个后缀树以便我们可以相对快速地计算重复项，我们仍然可以。

要实际生成数字，这种方法仍然是O(n^2). 但它会比您现有的大字符串方法更快，因为您只用小整数进行数学运算。将字符串转换为/从字符串转换为数千位数的数字并不是特别快......

所以这里有更多关于后缀树方法用于唯一子串计数的复杂性的详细信息。要做到正确要困难得多。

上面我们从字符串的末尾返回到开头，跟踪最后的余数。但这意味着特定数字与余数相加的内容取决于它在字符串中的位置。然而，在树中，给定节点与字符串末端的高度不同。这使得特定节点处的余数更难以计算。

我们需要做的是计算某种余数，其中当前数字的贡献取决于其高度，以保持当前数字的贡献固定。诀窍是将冒泡的可能余数集乘以代替。那么当且仅当从这里开始的数字可以被 整除时，我们才会得到 0 。什么意思？这意味着许多这样是。通过检查可以看出它适用于因为。我们总是可以通过反复试验找到逆。一般来说，它的存在和价值可以通过欧拉定理更有效地确定。无论哪种方式，在我们的例子中都是.10-1k10-1 (mod k)m(10*m) % k15750 = 7*7 + 15

现在将余数集乘以一个数字而不是当前数字的工作量更大，但这样做的好处是我们可以合并树的分支。例如，考虑 的后缀树 5271756。（请注意，唯一性很重要，因为字符串7出现了两次。）

(root):
  a
  b
  c
  d
  e
(a): '17'
  f
(b): '27'
  a
(c): '5'
  b
  e
(d): '7'
  a
  f
(e): '6'(end)
(f): '5'
  e

现在我们可以用我们的方式返回树找到余数的计数。756 的计算说明了这个想法：

digit  prev_remainders remainders
#                 for    6
6      {}              {(6)%7: 1}
#                 for    5         56
5      {6: 1}          {(5)%7: 1, (5+5*6)%7: 1}
                       {    5: 1,         0: 1} = {0:1, 5:1}
#                 for    7         756           75
7      {0: 1, 2:1}     {(7)%7: 1, (7+5*0)%7: 1, (7+5*5): 1}
                       {    0: 1,         0: 1,       4: 1} = {0:2, 4:1}

所以在这一点上，我们有 2 个可以被 0 整除的字符串，即7和756。

从根开始填充整棵树，然后以同样的方式冒泡（手工完成，我可能会犯错误——而且第一次犯了很多错误！）：

(root): {0:8, 1:6, 2:3, 4:1, 5:4, 6:4}
  a
  b
  c
  d
  e
(a): '17' {0:1, 1:3}
  f
(b): '27' {2:3, 6:3}
  a
(c): '5' {0:4, 1:3, 5:1}
  b
  e
(d): '7' {0:3, 4:1, 5:3}
  a
  f
(e): '6'(end) {6:1}
(f): '5' {0:1, 5:1}
  e

从中我们得出结论，存在可被8整除的子串7。事实上它们是：

175 (af)
5271 (cba)
52717 (cbaf)
5271756 (cbafe)
56 (ce)
7 (d)
7175 (daf)
756 (dcf)

剩下的呢？例如，有3获取的方法是什么意思2？这意味着，有3子s这样( (s%7) * (5^(len(s)-1)) ) %7 == 2。所以我们在最终答案中不需要它，但我们在中间计算中确实需要！