Как получить всю подстроку для данного регулярного выражения?

Question

Мне нужно, чтобы все подстроки соответствовали регулярному выражению, я знаю, что, вероятно, могу построить для него автомат, но я ищу более простое решение.
проблема в том, что Matcher.find () не возвращает все результаты.

String str = "abaca";
Matcher matcher = Pattern.compile("a.a").matcher(str);
while (matcher.find()) {
   System.out.println(str.substring(matcher.start(),matcher.end()));
}

Результат aba, а не aba,aca, как я хочу ...
есть идеи?
EDIT: другой пример: для string = abaa, regex = a. * a Я ожидаю получить aba, abaa, aa
p.s. если это не может быть достигнуто с помощью регулярных выражений, это также ответ, я просто хочу знать, что я не заново изобретаю колесо для чего-то, что язык уже дает мне ...

Answer 1

Вы можете сделать что-то вроде этого:

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static List<String> getAllMatches(String text, String regex) {
        List<String> matches = new ArrayList<String>();
        Matcher m = Pattern.compile("(?=(" + regex + "))").matcher(text);
        while(m.find()) {
            matches.add(m.group(1));
        }
        return matches;
    }

    public static void main(String[] args) {
        System.out.println(getAllMatches("abaca", "a.a"));
        System.out.println(getAllMatches("abaa", "a.*a"));
    }
}

который печатает:

[aba, aca]
[abaa, aa]

Единственное, что вам не хватает aba из последнего списка матчей. Это из-за жадных .* в a.*a. Вы не можете это исправить с помощью регулярных выражений. Вы можете сделать это, перебирая все возможные подстроки и вызывая .matches(regex) для каждой подстроки:

public static List<String> getAllMatches(String text, String regex) {
    List<String> matches = new ArrayList<String>();
    for(int length = 1; length <= text.length(); length++) {
        for(int index = 0; index <= text.length()-length; index++) {
            String sub = text.substring(index, index + length);
            if(sub.matches(regex)) {
                matches.add(sub);
            }
        }
    }
    return matches;
}

Если ваш текст останется относительно маленьким, это сработает, но для более крупных строк это может стать слишком вычислительным.

Answer 2

По умолчанию новое совпадение начинается в конце предыдущего.Если совпадения могут совпадать, необходимо указать начальную точку вручную:

int start = 0;
while (matcher.find(start)) { 
    ...
    start = matcher.start() + 1;
}

Answer 3

Это своего рода вычислительная проблема с открытым исходным кодом.Вопрос о всех возможных совпадениях для регулярного выражения можно перефразировать как

What are all the possible sub strings of a given String that match the given regex?

Так что ваш код действительно должен сделать (псевдокод):

for(String substring: allPossibleSubstrings) {
    if(PATTERN.matches(subString) {
        results.add(subString);
    }
}

Теперь для строкикак и abaa, это тривиально: AllPossible = ["a", "ab", "aba", "abaa", "ba", "baa", "aa"] Вы также можете добавить некоторый интеллект, ограничив размер подстрок минимальным размером, который может соответствовать регулярному выражению.Конечно, это будет расширяться экспоненциально для больших строк

Answer 4

Используйте matcher.find(startingFrom) в вашем цикле while и увеличьте начальную часть на единицу больше, чем в начале предыдущего матча: startingFrom = matcher.start()+1;