排除数字的算法

Question

你得到一个长整型数N（小于2^63-1）和50个其他整数。你需要找出从1到N中有多少个数字不包含这50个整数作为子串？

这是一道面试题目。

- user1499215

---

这里存在一个编程问题。 - btilly

@btilly 这真是一种解脱。也许问题可以进行编辑，以便像我这样的人能够明显地看到这只是一个数学问题？ - AakashM

很显然问题是要编写一个程序来进行计算。正如larsmans的答案所表明的那样，这涉及到许多编程理论。 - btilly

数学是计算机科学的基础。算法处于两者之间的边界上。没有理由将它们从这里排除。 - Kos

恭喜，版主们。无论在你们不注意的时候是否有足够的人来取消删除和重新开放这个问题，你们已经成功地让另一个贡献者离开了。再见。 - btilly

Answer 1

您没有指定进制，但我会假设十进制而不失一般性。

首先，请认识到这是一个字符串问题，而不是数字问题。

构建一个有限自动机A来识别50个整数作为其他字符串的子字符串。例如，两个整数44和3可以通过以下正则表达式识别为子字符串：

^.*(44|3).*$

构建一个有限自动机B来识别所有小于N的数字。例如，在十进制中识别1到27（包括27），可以通过编译RE实现

^([1-9]|1[0-9]|2[0-7])$

计算自动机 A 和 B 的交集 C，它也是一个有限自动机。

使用动态编程算法计算被C识别的语言的大小。用相同的算法计算被A识别的语言的大小，并将其从中减去。

（我并不声称这是渐近最优的，但它足以快速解决许多欧拉项目问题 :)

- Fred Foo

---

应该是1到27（包括27）而不是0到27。但是非常好的方法。它肯定比我想到的包含排除法好。 - btilly

抱歉，我不理解这个解决方案。你能用一个例子来解释一下吗？最好是一个更大的例子。另外，你能告诉我你动态规划解决方案的状态吗？ - user1499215

@larsmans，请您查看我的回复，尝试阐明您的解释，并给我反馈、纠正等。 - btilly

我认为你也可以用二叉决策图来实现这个功能 - 实际上，如果了解它们和有限状态机之间的联系，我不会感到惊讶。 BDD的一个优点是对它们的许多操作都有多项式保证。 - mcdowella

Answer 2

这只是对larsmans已经写过的内容的解释。如果你觉得这个答案不错，请投票支持他。

有限自动机（FA）仅是一组“状态”，并规定如果您处于状态S，并且接收到的下一个字符是c，则转换为状态T。其中两个状态是特殊的，一个是“从这里开始”，另一个是“成功匹配”。一个字符是特殊的，表示“字符串刚刚结束”。因此，您将使用一个字符串和一个有限自动机，在起始状态中启动，不断将字符输入到机器中并更改状态。如果在任何状态下给出了无法预期的输入，则匹配失败。如果您达到状态“I successfully matched”，则匹配成功。

现在有一种众所周知的算法，用于将正则表达式转换为有限自动机，该自动机仅在正则表达式匹配时才匹配字符串。（如果您阅读有关正则表达式的文章，则DFA引擎就是这样工作的。）为了说明，我将使用模式^.*（44 | 3）。* $“，这意味着”字符串的开头，任意数量的字符，后跟44或3，后跟任意数量的字符，最后跟字符串的结尾。“

首先让我们标记在寻找下一个字符时可以在正则表达式中的所有位置：^ A。*（4 B 4 | 3）C。* $

我们正则表达式引擎的状态将是这些位置的子集，特殊状态匹配。状态转换的结果将是我们可以到达的状态集合，如果我们在该位置并看到特定字符，则会发生转换。我们的起始位置位于RE开头，即{A}。以下是可以到达的状态：

S1: {A}   # start
S2: {A, B}
S3: {A, C}
S4: {A, B, C}
S5: matched

以下是转换规则：

S1:
  3: S3
  4: S2
  end of string: FAIL
  any other char: S1
S2:
  3: S3
  4: S3
  end of string: FAIL
  any other char: S1
S3:
  4: S4
  end of string: S5 (match)
  any other char: S3
S4:
  end of string: S5 (match)
  any other char: S4

现在，如果您拿任何字符串，从状态S1开始，并遵循规则，您将匹配该模式。这个过程可能会很长而繁琐，但幸运的是可以自动化。我猜larsmans已经为自己的使用自动化了它。（技术说明：从“RE中的位置”扩展到“可能处于的位置集合”的过程可以在前期或运行时完成。对于大多数RE来说，最好在前期完成，就像这里一样。但是微小部分的病态示例将得到非常多的状态，最好在运行时完成。）

我们可以使用任何正则表达式来做到这一点。例如，^([1-9]|1[0-9]|2[0-7])$可以标记为：^A([1-9]|1B[0-9]|2C[0-7])D$，并且我们得到以下状态：

T1: {A}
T2: {D}
T3: {B, D}
T4: {C, D}

转换和过渡效果：

T1:
  1: T3
  2: T4
  3-9: T2
  any other char: FAIL
T2:
  end of string: MATCH
  any other char: FAIL
T3:
  0-9: T2
  end of string: MATCH
  any other char: FAIL
T4:
  0-7: T2
  end of string: MATCH
  any other char: FAIL

好的，我们知道什么是正则表达式，有限自动机及它们之间的关系。两个有限自动机的交集是什么？它只是一个有限自动机，在两个有限自动机分别匹配时匹配，并在其他情况下无法匹配。它很容易构建，其状态集只是一个在一个中的状态和另一个中的状态的成对集合。它的转移规则是独立地应用每个成员的转移规则，如果其中任何一个失败，则整个都失败，如果两个都匹配，则两者都匹配。

对于上述一对，让我们实际执行数字13的交集。我们从状态(S1, T1)开始。

state: (S1, T1)  next char: 1
state: (S1, T3)  next char: 3
state: (S3, T2)  next char: end of string
state: (matched, matched) -> matched

接着在数字14上进行操作。

state: (S1, T1)  next char: 1
state: (S1, T3)  next char: 4
state: (S2, T2)  next char: end of string
state: (FAIL, matched) -> FAIL

现在我们来到了重点。鉴于最终的有限状态自动机，我们可以使用动态规划算法来计算与其匹配的字符串数量。以下是该计算过程：

0 chars:
  (S1, T1): 1
    -> (S1, T3): 1 # 1
    -> (S1, T4): 1 # 2
    -> (S3, T2): 1 # 3
    -> (S2, T2): 1 # 4
    -> (S1, T2): 5 # 5-9
1 chars:
  (S1: T2): 5      # dead end
  (S1, T3): 1
    -> (S1, T2): 8 # 0-2, 5-9
    -> (S2, T2): 1 # 3
    -> (S3, T2): 1 # 4
  (S1, T4): 1
    -> (S1, T2): 6 # 0-2, 5-7
    -> (S2, T2): 1 # 3
    -> (S3, T2): 1 # 4
  (S2, T2): 1      # dead end
  (S3, T2): 1
    -> match:    1 # end of string
2 chars:
  (S1, T2): 14     # dead end
  (S2, T2): 2      # dead end
  (S3, T2): 2
    -> match     2 # end of string
  match:    1
    -> match     1 # carry through the count
3 chars:
  match:    3

好的，这是很多工作，但我们发现有3个字符串同时符合这两条规则。而且我们以一种可自动化和可扩展到更大数量的方式完成了它。

当然，我们最初提出的问题是有多少个匹配第二个规则但不匹配第一个规则。我们知道有27个符合第二个规则，3个符合两个规则，因此有24个必须符合第二个规则但不符合第一个规则。

正如我之前所说，这只是larsmans的解决方案阐述。如果你学到了东西，请为他点赞，投票支持他的答案。如果这些材料听起来有趣，请购买像《程序语言实践》这样的书籍，学习更多关于有限自动机、解析、编译等方面的知识。这是一个非常好的技能集，很多程序员都没有掌握。

- btilly