числа Нахождение Фибоначчи с использованием регулярных выражений

Question

Я нашел следующий пример кода на this blog post:

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|^.))* .. Как работает матч чисел Фибоначчи?

Answer 1

(?x) .? | (\\2?+ (\\1|^.))* .. 

Здесь есть много вещей, которые могут смутить. Я рассмотрю каждую из этих вещей, чтобы объяснить, почему работает алгоритм.

1. Матч выполняется по строке с длиной регулярного выражения, а не по фактическому номеру. Единственными реальными данными в строке являются ее длина.

2. \\ Двойные обратные косые черты - это просто потому, что в строковых литералах строки должны быть обратными слэшами, чтобы было ясно, что вы не избегаете чего-то другого. Я не буду показывать их в любом будущем коде в этом ответе.

3. (?x): Это позволяет расширенный режим регулярного выражения. В этом режиме пробелы, которые не являются обратными или внутри символьного класса, игнорируются, позволяя регулярному выражению разбиваться на более читаемые части со встроенными комментариями. [sarand.com].

4. .?: Это будет соответствовать 0 или 1 символьным строкам. Это совпадение используется только для случаев f (0), f (1) и f (2), иначе оно будет отброшено.

5. |: Это означает, что если первая попытка совместить 1 или два символа не сработала, попробуйте сопоставить все, что находится справа от нее.

6. (: Это открывает первую группу (см. Далее \1).

7. (\2?++ делает ? притяжательным квантором. В этом случае результат заключается в том, что ? означает использование обратной ссылки \2, если оно определено, а средства + не возвращаются и не пытаются использовать его, если регулярное выражение не работает с ним.

8. (\1|^.): Это будет соответствовать либо всем, что было согласовано до сих пор, либо одному персонажу. Это, конечно, означает, что первое «все, что соответствует до сих пор» - это один символ. Так как это второе регулярное выражение, оно также является новым \2

9. )*: Это повторит алгоритм. Каждый раз, когда он повторяется, он будет определять новые значения для \1 и \2. Эти значения будут равны F (n-1) и F (n-2) для текущей итерации, которая будет F (n). Каждая итерация будет добавлена ​​к предыдущей, что означает, что у вас есть сумма F (n) от 0 до n. Попробуйте запустить алгоритм через голову для получения меньших чисел, чтобы получить эту идею.

10. ..: Одна точка требуется в соответствии с п (1), который не входит в сумму, во-вторых, потому, что Second Identity of Fibonacci Numbers утверждает, что сумма последовательности чисел Фибоначчи является fibonnaci число минус один.(1)

    

11. Прогулка по замене вы можете увидеть, как это будет продолжаться, чтобы добавить числа Фибоначчи до заполнения строки. Первая итерация соответствует ^., поэтому 1. Вторая итерация соответствует предыдущему партиальному совпадению с \2, а также всему предыдущему матчу с \1. Это делает два для второй итерации. Третья итерация занимает эту вторую часть матча со второй итерации (1), а также всю вторую итерацию (2). Это делает три для третьей итерации. Добавьте итерации вместе, и у вас есть сумма чисел фиб.

Для получения дополнительной информации о том, почему этот рецидив действительно работает, см. Why does Java regex engine throw StringIndexOutOfBoundsException on a + repetition?.