Идентификатор ошибки 6984178
Существует много ошибок, связанных с броском двигателя StringIndexOutOfBoundsException ( см. Результаты поиска . Эта ошибка, в частности, была зарегистрирована и принята как Идентификатор ошибки 6984178 (может потребоваться некоторое время, чтобы это появилось во внешней базе данных).
Вот гораздо более простой шаблон, который воспроизводит ошибку ( см. Также на ideone.com ):
System.out.println(
"abaab".matches("(?x) (?: (?=(a+)) \\1 b )* x")
); // StringIndexOutOfBounds: -1
Обратите внимание, что использование *? или *+ просто возвращает false, как и ожидалось.
Похоже, что проблема вызвана попыткой отследить жадныйповторение, когда есть ссылка на группу захвата внутри предвидения: индекс вне границ - это разница в длине между первым и вторым a+ (например, "aabaaaaab" получает -3).
Oneвероятно, придется отладить исходный код java.util.regex.Pattern , чтобы точно определить природу ошибки.
Изучение паттерна Фибоначчи
В движке Java,с жадным возвратом +
Вот более подробный фрагмент, показывающий, как помешивает движок на этом шаблоне:
String FIBONACCI =
"(?x) .{0,2} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+ . ";
for (int n = 0; n < 1000; n++) {
String s = new String(new char[n]);
try {
if (s.matches(FIBONACCI)) {
System.out.printf("%n%s", n);
}
} catch (StringIndexOutOfBoundsException e) {
String index = e.getMessage().replace("String index out of range: ", "");
System.out.printf(" <%s:%s>", n, index);
}
}
(слегка отредактированный) вывод (, как видно на ideone.com ):
0 1 2 3 <5:-1>
6 <7:-1> ... <12:-1> <13:-3>
14 <15:-3> ... <33:-3> <34:-8>
35 <36:-8> ... <88:-8> <89:-21>
90 <91:-21> ... <232:-21> <233:-55>
234 <235:-55> ... <609:-55> <610:-144>
611 <612:-144> ...
Так что каким-то образом движок пытается получить доступ к строковым индексам в -1, -3, -8, -21, -55, -144 и т. Д. Обратите внимание, что это все остальные числа Фибоначчи,но отрицательно.Также обратите внимание, что после первых нескольких чисел остальные совпадения (6, 14, 35, ...) являются НЕ числами Фибоначчи.
В движке .NETс жадным обратным отслеживанием +
Хотя шаблон изначально был написан с учетом необходимости обладания квантификатором, на самом деле повторение обратного отслеживания все равно даст правильный ответ (при условии, что механизм не глючит, как в Java),Вот реализация C # на движке .NET ( см. Также на ideone.com ):
Regex r = new Regex(
@"(?x) ^.{0,1}$ | ^(?: (?=(\2?)) (?=(\2\3|^.)) (?=(\1)) \2)+ . $ "
);
for (int n = 0; n < 1000; n++) {
if (r.IsMatch("".PadLeft(n))) {
Console.Write("{0} ", n);
}
}
// 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
Как видите, выходные данные верны, даже с возвратом +«петля».На самом деле, именно потому, что это цикл возврата, особый случай может быть ограничен только .{0,1} вместо .{0,2}.
На движке Java с неохотным возвратом +?
Это работает в Java, как и ожидалось.Кроме того, поскольку он неохотно, мы также можем ограничить специальный случай до .{0,1} ( см. Также на ideone.com ):
String FIBONACCI =
"(?x) .{0,1} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+? . ";
Об алгоритме
Формула
В паттерне используется Вторая идентичность чисел Фибоначчи :
Это можно доказать по индукции.
Паттерн
Давайте использовать эту версию паттерна (которая работает в Java, а при привязке также работает в C #):
summation
free-space! "loop"
↓ ↓
(?x) .{0,1} | (?: (?=(\2|^)) (?=(\2\3|^.)) (?=(\1)) \2)+? .
\____/ \___________________________________/ ↑ ↑
base case inductive case +Fi +1
for n = 0,1
(assertions don't "count" toward sum)!
$1 := $2 (or initialized with 0)
$2 := $2+$3 (or initialized with 1)
$3 := $1 (a temporary variable for the "swap")
Генерация последовательности Фибоначчипрост, основан на переходе [$1, $2] := [$2, $2+$1].Поскольку утверждения выполняются последовательно, вводится временная переменная (так же, как версия с псевдокодом для одного присваивания).