Не ответ, просто упомяну, что «очевидные» регулярные выражения для этого (как опубликовано выше) имеют неприятное квадратичное поведение в худшем случае (хотя я почти уверен, что вы не имеете дело с такими вырожденными случаями, но это интересно само по себе).
Вот небольшой график, который я подготовил:
альтернативный текст http://img517.imageshack.us/img517/1158/imageerp.jpg
Я использовал строки вида "111..1111a2"
Есть J
вхождений '1'.
Причина плохой производительности очевидна: помощник продолжает видеть 1 с и радостно думает, что он добьется успеха, и только когда он находит a
почти в конце, он обнаруживает, что a
не соответствует $
, таким образом, он проходит весь путь назад и начинается со второго символа.
Первоначально я думал, что притяжательные квантификаторы здесь помогут, но это не выглядит прямо. Даже если я напишу \d++
, если я вызову matcher.find (), он все равно попытается сопоставить шаблон , начиная с каждого индекса , т. Е. Внешний цикл не получает подсказок от предыдущих сбоев позитивных квантификаторов , (Обратите внимание, что эта проблема не влияет на Matcher.matches (), так как он пытается сопоставить только по одному индексу, началу).
В этой конкретной задаче, чтобы избежать такого поведения, мы должны были бы перевернуть строку и выполнить поиск по простому шаблону ^\\d+
или выполнить итерацию символов назад и выполнить ручное сопоставление.