Как найти последнее вхождение набора символов в строке с помощью регулярных выражений в Java? - PullRequest
Новая
       41

Как найти последнее вхождение набора символов в строке с помощью регулярных выражений в Java?

6 голосов
/ 04 июня 2019

Мне нужно найти последний индекс набора символов в строке.Рассмотрим набор символов: x, y, z и строку как Vereador Luiz Pauly Home , тогда мне нужен индекс как 18 .

для поиска индекса я создал шаблон с флагом DOTALL и жадным квантификатором как (? s). * (x | y | z) .Когда шаблон применяется к этой строке (многострочный), я могу узнать индекс из начальной группы.Код: 

int findIndex(String str){
  int index = -1;
  Pattern p = Pattern.compile("(?s).*(x|y|z)");
  Matcher m = regex.matcher(str);
  if(m.find()){
    index = m.start(1);
  }
  return index;
}

Как и ожидалось, он правильно возвращает значения, если есть совпадение.

Но если совпадения нет, то это занимает слишком много времени (17 минут для 600000 символов) , поскольку это совпадение Жадности.

Я пробовал с другими квантификаторами, но не могу получить желаемый результат. Так может ли кто-нибудь отослать какое-нибудь лучшее регулярное выражение?

PS: Я также могу подумать о том, чтобы просмотреть содержимое из прошлого и найти индекс. Но я надеюсь, что в регулярном выражении есть лучший способ, который может сделатьработа быстро.

Ответы [ 3 ]

3 голосов
/ 04 июня 2019

Проблемы производительности с регулярным выражением (?s).*(x|y|z) происходят из-за того, что шаблон .* является первым подшаблоном, который сначала захватывает всю строку, а затем происходит обратное отслеживание для поиска x, y или z.Если совпадения нет или совпадение находится в начале строки, а строки очень большие, это может занять очень много времени.

Шаблон ([xyz])(?=[^xyz]*$) кажется немного лучше: онзахватывает x, y или z и утверждает, что нет других x, y или z до конца строки, но это также несколько ресурсоемко из-за каждой проверкипосле того, как совпадение найдено.

Самое быстрое регулярное выражение для выполнения вашей работы: 

^(?:[^xyz]*+([xyz]))+

Это соответствует

  • ^ - начало строки
  • (?:[^xyz]*+([xyz]))+ - 1 или более повторений
    • [^xyz]*+ - любые 0 или более символов, отличных от x, y и z, сопоставлены собственнически (никакого возврата к шаблону нетразрешено)
    • ([xyz]) - группа 1: x, y или z.

Значение и данные группы 1 будут принадлежатьдо последней итерации повторяющейся группы (так как все предыдущие данные перезаписываются с каждой последующей итерацией).

2 голосов
/ 04 июня 2019

Существует несколько способов решения проблемы, и наилучший способ будет зависеть от размера входных данных и сложности шаблона:

  1. Обратный ввод строки и, возможно, шаблон, это может работать для не сложных шаблонов. К сожалению, java.util.regex не позволяет сопоставить шаблон справа налево.

  2. Вместо использования жадного квантификатора просто сопоставьте шаблон и цикл Matcher.find(), пока не будет найдено последнее вхождение.

  3. Используйте другой движок регулярных выражений с лучшей производительностью, например, RE2 / J: сопоставление регулярного выражения с линейным временем в Java .

Если вариант 2 недостаточно эффективен для вашего случая, я бы предложил попробовать RE2 / J:

Стандартный пакет регулярных выражений Java, java.util.regex и многие другие широко используемые пакеты регулярных выражений, такие как PCRE, Perl и Python, используют стратегию реализации обратного отслеживания: когда шаблон представляет две альтернативы, такие как a|b, движок сначала попытается сопоставить подшаблон a, и если это не даст совпадения, он сбросит входной поток и попытается сопоставить b.

Если такие варианты глубоко вложены, эта стратегия требует экспоненциального числа проходов по входным данным, прежде чем она сможет определить, совпадает ли входной. Если ввод велик, легко построить шаблон, время выполнения которого превысит время жизни юниверса. Это создает угрозу безопасности при приеме шаблонов регулярных выражений из ненадежных источников, таких как пользователи веб-приложения.

Напротив, алгоритм RE2 исследует все совпадения одновременно за один проход по входным данным с использованием недетерминированного конечного автомата.

1 голос
/ 04 июня 2019

StringBuilder имеет reverse и является CharSequence, поэтому поиск возможен. 

Pattern p = Pattern.compile("[xyz]");
StringBuilder sb = new StringBuilder(str).reverse();
Matcher m = p.matcher(sb);
return m.find() ? sb.length() - m.end() : -1;

К сожалению, обращение дорого стоит.

Решение без регулярных выражений, вероятно, быстрее.

(Кстати, суррогатные пары корректно обрабатываются с помощью реверса.)

...