排除数字的算法

Question

给出一个整数N,它适合长(小于2 ^ 63-1)和50个其他整数.你的任务是找到从1到N的多少个数字不包含50个数字作为其子串？

这个问题来自一次采访.

Answer 1

你没有指定基数,但我会假设小数而不失一般性.

首先,要认识到这是一个字符串问题,而不是数字问题.

构建有限自动机A以将50个整数识别为其他字符串的子串.例如,两个整数44和3被RE识别为子串

^.*(44|3).*$

构建有限自动机B以识别小于N的所有数字.例如,以十进制识别1到27(包括),这可以通过编译RE来实现

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

计算自动机A和B的交点C,它又是FA.

使用动态编程算法计算C识别的语言大小.从A识别的语言大小中减去该值,由同一算法计算得出.

(我并不是说这是渐近最优的,但它足以解决许多Project Euler问题:)

Answer 2

这只是larsmans已写的内容的解释.如果您喜欢这个答案,请另外投票给他.

有限自动机FA只是一组状态,并且规则说如果你处于状态S并且你被喂食的下一个字符就是c你转换到状态T.其中两个州很特别.一个意思是"从这里开始",另一个意思是"我成功匹配".其中一个字符是特殊的,意思是"字符串刚刚结束".所以你拿一个字符串和一个有限的自动机,从起始状态开始,继续将字符输入机器并改变状态.如果您提供任何状态意外输入,则无法匹配.如果您达到"我成功匹配"状态,您就会成功匹配.

现在有一个众所周知的算法,用于将正则表达式转换为匹配字符串的有限自动机,当且仅当该正则表达式匹配时.(如果您已经阅读过正则表达式,这就是DFA引擎的工作方式.)为了说明我将使用的模式^.*(44|3).*$意味着"字符串的开头,任意数量的字符,后跟44或3,后跟任意数字字符串,后跟字符串的结尾."

首先,当我们寻找下一个字符时,让我们标记我们可以在正则表达式中的所有位置:^A .*(4B 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解决方案的阐述.如果你学到了什么,就投票给他,投票给他答案.如果这些材料听起来很有意思,那就去买一本像Progamming Language Pragmatics这样的书,学习更多关于有限自动机,解析,编译等的知识.这是一个非常好的技能组合,并且有太多的程序员没有.