Все перекрывающиеся подстроки, соответствующие регулярному выражению java

Question

Есть ли метод API, который возвращает все (возможно перекрывающиеся) подстроки, которые соответствуют регулярному выражению?

Например, у меня есть текстовая строка: String t = 04/31 412-555-1235;, и у меня есть шаблон: Pattern p = new Pattern("\\d\\d+");, который соответствует строкам двух или более символов.

Спички я получаю: 04, 31, 412, 555, 1235.

Как получить перекрывающихся матчи?

Я хочу код возврата: 04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35.

Теоретически это должно быть возможным - существует очевидный алгоритм O(n^2), который перечисляет и проверяет все подстроки по шаблону.

EDIT

Вместо перечисления всех подстрок, безопаснее использовать метод region(int start, int end) в Matcher. Проверка шаблона на отдельную извлеченную подстроку может изменить результат совпадения (например, если в начале/конце шаблона есть негравифицирующая группа или проверка границы слов).

EDIT 2

На самом деле, неясно, имеет ли region(), что вы ожидаете для нулевой ширины спичек. Спецификация является неопределенной, и эксперименты дают неутешительные результаты.

Например:

String line = "xx90xx"; 
String pat = "\\b90\\b"; 
System.out.println(Pattern.compile(pat).matcher(line).find()); // prints false 
for (int i = 0; i < line.length(); ++i) { 
    for (int j = i + 1; j <= line.length(); ++j) { 
    Matcher m = Pattern.compile(pat).matcher(line).region(i, j); 
    if (m.find() && m.group().size == (j - i)) { 
     System.out.println(m.group() + " (" + i + ", " + j + ")"); // prints 90 (2, 4) 
    } 
    } 
} 

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

EDIT 3

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

public static void allMatches(String text, String regex) 
    { 
    for (int i = 0; i < text.length(); ++i) { 
     for (int j = i + 1; j <= text.length(); ++j) { 
     String positionSpecificPattern = "((?<=^.{"+i+"})("+regex+")(?=.{"+(text.length() - j)+"}$))"; 
     Matcher m = Pattern.compile(positionSpecificPattern).matcher(text); 

     if (m.find()) 
     { 
      System.out.println("Match found: \"" + (m.group()) + "\" at position [" + i + ", " + j + ")"); 
     } 
     } 
    } 
    } 

EDIT 4

Вот лучший способ сделать это: https://stackoverflow.com/a/11372670/244526

EDIT 5

JRegex библиотека поддерживает поиск всех перекрывающихся подстроки совпадающие с Java регулярное выражение (хотя он, похоже, не обновлялся в то время).В частности, documentation on non-breaking search указует:

Использования неразрывного поиска вы можете найти все возможное occureneces из в модели, в том числе тех, которые пересекаются или вложенными. Это , достигнутый с использованием метода Matcher.()

Answer 1

Ближайшее, что вы можете получить, это примерно так.

"(?=((\\d*)\\d))(?=(\\d)\\d*)" 

Результат будет в захвате группы 1, 2 и 3.

Насколько мое воображение может пойти, я могу только думать о захвате в нулевой длины утверждение как жизнеспособный способ вернуть себе такое же положение строки. Захват текста за пределами утверждения с нулевой длиной будет потреблять текст раз и навсегда (look-behind может записывать фиксированную длину только в Java, поэтому он может считаться недоступным).

Это решение не является совершенным: кроме повторения (текста в одном и том же положении!) И пустых совпадений строк он не будет захватывать все возможные подстроки.

Один из способов, чтобы захватить все возможные подстроки являются построить следующее регулярное выражение со значением п, начиная с 1:

"(?=(\\d{" + n + "}))" 

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

Этот метод, конечно, неэффективен по сравнению с методом сопоставления всех чисел с помощью «\ d +» и извлекает всю подстроку.

Answer 2

Это выполнимо, как O (N)только если указать диапазон разрешенных длины номера.

Скажем, из 2-4 цифр (номера 00-9999): (?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)

Это нулевой длины утверждение через положительный предпросмотр, захватив такое предпросмотр в группы. Результатом является массив из всех 2-4-разрядных строк, которые можно найти в вводе регулярных выражений вместе с дубликатами и пустыми строками (для не-совпадений).

Я не разработчик Java, но я считаю, что скрипт Perl можно также прочитать в качестве примера.

#!/usr/bin/perl          # perl script 
use List::MoreUtils qw/ uniq /;      # uniq subroutine library 
$_ = '04/31 412-555-1235';       # input 
my @n = uniq (/(?=(\d{2}))(?=(\1\d)?)(?=(\2\d)?)/g); # regex (single slash in Perl) 
print "$_\n" for grep(/\S/, @n);      # print non-empty lines 

Этот трюк использует обратные ссылки. Если вы хотите захватить 2-5-значную строку, вам нужно будет использовать еще один положительный результат в регулярном выражении: (?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)(?=(\\3\\d)?).

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

Answer 3

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

if (textToParse != null) { 
Matcher matcher = PLACEHOLDER_PATTERN.matcher(textToParse); 
    while(matcher.hitEnd()!=true){ 
     Boolean result = matcher.find(); 
     int count = matcher.groupCount(); 
     System.out.println("Result " +result+" count "+count); 
     if(result==true && count==1){ 
      mergeFieldName = matcher.group(1); 
      mergeFieldNames.add(mergeFieldName); 
      } 
     } 
    } 

Я использовал метод matcher.hitEnd(), чтобы проверить, если я достиг конца текста.

Надеюсь, что это поможет. Спасибо!