18

このブログ投稿で次のコード例を見つけました。

final String FIBONACCI = 
   "(?x) .? | ( \\2?+ (\\1|^.) )* ..";

for (int n = 0; n < 10000; n++) {
   String s = new String(new char[n]);
   if (s.matches(FIBONACCI)) {
      System.out.printf("%s ", n);
   }
}

出力：0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...

はどのように(?x) .? | ( \\2?+ (\\1|^.) )* ..フィボナッチ数に一致しますか?

4

2 に答える 2

0

他の回答ですでに詳細に説明されていることは知っていますが（一般的に使用される正規表現のより良い説明を含む）、最近、説明なしでこの正規表現に出くわしたので、自分でコメントを追加しました。他の人が見られるように、ここで共有することも考えました。

最初に注意すべきことは、正規表現が整数に単項を使用することです。したがってString s = new String(new char[n]);、Java コードでは、整数nをその数の ( '\0') 文字の文字列に変換します。この文字列に含まれる文字は重要ではありません。単項にとって重要なのは長さです。(Java 11+ の代替手段は、たとえば であった可能性がString s = "x".repeat(n);あり、それでも意図したとおりに機能します。)

正規表現自体については：

"(?x) .? | ( \\2?+ (\\1|^.) )* .." # Since this is a Java-String, where the `\` are escaped
                                   # as `\\` and `String#matches` also implicitly adds a 
                                   # leading/trailing `^...$` to regex-match the entire
^(?x) .? | ( \2?+  (\1 |^.) )* ..$ # String, the actual regex will be this:
                                   # The `(?x)` is used to enable comments and whitespaces,
                                   # so let's ignore those for now:
^.?|(\2?+(\1|^.))*..$
    (           )*                 # First capture group repeated 0 or more times.
                                   # On each iteration it matches one Fibonacci number.
            |^.                    # In the first iteration, we simply match 1 as base case.
                                   # Afterwards, the ^ can no longer match, so the
                                   # alternative is used.
     \2?+                          # If possible, match group 2. This ends up being the
                                   # Fibonacci number before the last. The reason we need
                                   # to make his optional is that this group isn't defined
                                   # yet in the second iteration. The reason we have the `+`
                                   # is to prevent backtracking: if group 2 exists, we
                                   # *have* to include it in the match, otherwise we would
                                   # allow smaller increments.  
         (\1|  )                   # Finally, match the previous Fibonacci number and store
                                   # it in group 2 so that it becomes the second-to-last
                                   # Fibonacci number in the next iteration.

                                   # This in total ends up adding Fibonacci numbers starting
                                   # at 1 (i.e. 1,2,3,5,8,... will add up to 3,6,11,19,...
                  ..               # They are all two less than the Fibonacci numbers, so
                                   # we add 2 at the end.

                                   # Now it's only missing the 0 and 1 of the Fibonacci
 .?|                               # numbers, so we'll account for those separately
于 2020-05-15T08:19:17.477 に答える