20

long (2^63-1 未満) と 50 個の他の整数に収まる整数 N が与えられます。あなたの課題は、部分文字列として 50 個の数字のいずれも含まない 1 から N までの数字の数を見つけることです。

この質問はインタビューからのものです。

4

2 に答える 2

22

基数を指定していませんが、一般性を失うことなく 10 進数を想定します。

まず、これは文字列の問題であり、数値の問題ではないことを認識してください。

有限オートマトンAを構築して、50 個の整数を他の文字列の部分文字列として認識します。たとえば、2 つの整数 44 と 3 は、RE によって部分文字列として認識されます。

^.*(44|3).*$

N未満のすべての数値を認識する有限オートマトンBを作成します。たとえば、10 進数で 1 から 27 (両端を含む) を認識するには、RE をコンパイルすることで実現できます。

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

オートマトンAとBの交点Cを計算します。これが FA になります。

動的計画法アルゴリズムを使用して、Cによって認識される言語のサイズを計算します。同じアルゴリズムで計算された、Aによって認識される言語のサイズからそれを引きます。

(これが漸近的に最適であると主張しているわけではありませんが、多くの Project Euler の問題を解決するのに十分な速さでした:)

于 2012-07-03T15:39:50.263 に答える
22

これは、larsmans がすでに書いたことの説明にすぎません。この回答が気に入ったら、さらに彼に投票してください。

有限オートマトン FA は状態の集合であり、ルールは、あなたが状態Sにいて、次のキャラクターが与えられた場合、あなたはc状態に遷移するというものですT。そのうちの 2 つの州は特別です。1 つは「ここから始める」という意味で、もう 1 つは「マッチングに成功しました」という意味です。文字の 1 つは特別で、「文字列がちょうど終了した」ことを意味します。したがって、文字列と有限オートマトンを使用して、開始状態から開始し、文字をマシンに送り続けて状態を変更します。状態に予期しない入力を与えると、一致に失敗します。「マッチング成功」の状態になったらマッチング成功です。

現在、正規表現が一致する場合にのみ文字列に一致する有限オートマトンに正規表現を変換するためのよく知られたアルゴリズムがあります。(正規表現について読んだことがあれば、これが DFA エンジンのしくみです。) 説明するため^.*(44|3).*$に、「文字列の開始、任意の数の文字、その後に 44 または 3 のいずれか、その後に任意の数字が続く」という意味のパターンを使用します。文字列の末尾が続きます。」

最初に、次の文字を探すときに正規表現で取りうるすべての位置にラベルを付けましょう: ^A .*(4B 4|3)C.*$

正規表現エンジンの状態は、これらの位置のサブセットになり、特別な状態が一致します。状態遷移の結果は、その位置にいて特定のキャラクターを見た場合に到達できる一連の状態になります。開始位置は、{A} である RE の先頭です。到達できる状態は次のとおりです。

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

文字列を取り、それを state で開始しS1、ルールに従うと、そのパターンに一致します。このプロセスは長くて面倒ですが、幸いなことに自動化できます。私の推測では、larsmans は自分で使用するためにそれを自動化しました。(技術的な注意として、「RE 内の位置」から「あなたがいる可能性のある一連の位置」への拡張は、ここのように事前に行うことも、実行時に行うこともできます。ほとんどの RE では、事前に行う方がよいでしょう) 、ここのように。しかし、異常な例のごく一部は非常に多数の状態で終わるため、実行時にそれらを行う方が良い場合があります.)

これは、任意の正規表現で行うことができます。たとえば、A B C D^([1-9]|1[0-9]|2[0-7])$というラベルを付けると、次の状態が得られます。^([1-9]|1[0-9]|2[0-7])$

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

これで、正規表現とは何か、有限オートマトンとは何か、そしてそれらがどのように関係するかがわかりました。2 つの有限オートマトンの交点は何ですか? 両方の有限オートマトンが個別に一致する場合は一致し、それ以外の場合は一致しないのは、単なる有限オートマトンです。構成は簡単で、その状態のセットは、一方の状態と他方の状態のペアのセットです。その移行ルールは、各メンバーに個別に移行ルールを適用するだけで、どちらかが失敗した場合は全体が適用され、両方が一致した場合は両方が適用されます。

上記のペアについて、実際に number の交点を実行してみましょう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 つあることがわかりました。そして、自動化可能で、より大きな数に拡張できる方法でそれを行いました。

もちろん、最初に提起された問題は、2 番目に一致し、1 番目に一致しなかったものがいくつあるかということでした。27 は 2 番目のルールに一致し、3 は両方に一致するため、24 は最初のルールではなく 2 番目のルールに一致する必要があります。

前に言ったように、これは解明された larsmans ソリューションにすぎません。何かを学んだ場合は、彼に賛成票を投じ、彼の答えに投票してください。この資料が興味深いと思われる場合は、 Progamming Language Pragmaticsのような本を購入して、有限オートマトン、構文解析、コンパイルなどについて詳しく学んでください。持っていると非常に優れたスキルセットですが、持っていないプログラマーが多すぎます。

于 2012-07-03T19:26:13.523 に答える