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

Мне нужно получить все подстроки, соответствующие регулярному выражению, я знаю, что я могу построить для него автомат, но я ищу более простое решение. Проблема заключается в том, что 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: другой пример: для строки = abaa, regex = a. * a Я ожидаю получить aba, abaa, aa
P.S. если он не может быть достигнут с помощью регулярных выражений, это также ответ, я просто хочу знать, что я не заново изобретаю колесо для чего-то, что уже дал мне язык...

Ответы

Ответ 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;
}

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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"] Вы также можете добавить некоторый интеллект, ограничив размер подстрок минимальным размером, который может быть сопоставлен регулярным выражением. Конечно, это будет экспоненциально расширяться для больших строк