## Monday, September 13, 2010

### Finding Fibonacci numbers using regex

This is one of the more fun patterns I've written; it exploits the Second Identity of Fibonacci Numbers. ```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
```

I should probably elaborate more on this for stackoverflow someday, but here are important variations of the pattern:
```(?x) .? | (     \2?+ (\1|^.) )* ..
// possessive optional forward reference (Java, PCRE)

(?x) .? | (  (?>\2?) (\1|^.) )* ..
// greedy optional forward reference in an atomic group (Java, .NET, PCRE)

(?x) .? | ( (?:\2|^) (\1|^.) )* ..
// non-optional forward reference with explicit first iteration alternative (Java, .NET, PCRE)
```
The main purpose of making the forward reference optional in the first two patterns is to make it through the first iteration (before group 2 even captures anything). However, this also has the side effect of allowing it to opt out at the last iteration. In this setup, this is not a problem since `\1` is always at least as long as `\2`, so if we're forced to opt out of matching `\2`, we can never then match `\1`.

Needless to say, it's crucial that the optional forward reference is non-backtrackable, because opting out on any iteration but the last would cause mismatches.

#### 1 comment:

1. Your algorithm got a question on stackoverflow and I did my best to answer it: http://stackoverflow.com/questions/18623801/finding-fibonacci-numbers-using-regex

Let me know if my analysis seems correct to you.

Thanks,

James