Поиск всех соответствующих подстрок, а не только "самый расширенный"

Ответ 1

Вы можете использовать неохотные квалификаторы, такие как *? и +?. Они соответствуют как можно меньше, в отличие от стандартных * и +, которые являются жадными, т.е. Соответствуют как можно больше. Тем не менее, это позволяет вам находить определенные "под-матчи", причем не все из них. Еще один контроль может быть достигнут с помощью контрольных групп, не связанных с захватом, также описанных в документах. Но для того, чтобы действительно найти все подзаголовки, вам, вероятно, придется самому заниматься, т.е. Построить автомат, которому соответствует регулярное выражение, и перемещаться по нему с помощью пользовательского кода.

Ответ 2

Вам понадобится ленивый квантификатор.

Попробуйте следующее:

Pattern p = Pattern.compile("(a )+(b )+((c )*?)c");

Также обратите внимание, что я снова сгруппировал "c", так как я думаю, что вы хотите. В противном случае вы найдете произвольно много пробелов, но не "c".

Ответ 3

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

Ответ 4

Я не знаю никаких двигателей регулярных выражений, которые могут вернуть все допустимые соответствия.

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

Кандидат строится путем перечисления всей возможной подстроки заданного ввода.

var str = "y z a a a b c c z y z a a a b c c z";
var regex = new Regex("(a )+(b )+(c *)c");

var length = str.Length;

for (int start = 1; start <= length;start++){

    for (int groupLength = 1;  start + groupLength - 1 <= length ;groupLength++){

        var candidate = str.Substring(start-1,groupLength); //.Dump();

        //("\"" + candidate + "\"").Dump();

        var match = regex.Match(candidate);

        if (match.Value == candidate )
        {
            candidate.Dump();
        }

    }
}

Это дает

a a a b c c 
a a b c c 
a b c c 

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

a a a b c => I state that this is not a match
a a b c c ok
a a b c => I state that this is not a match
a b c c ok
a b c => I state that this is not a match

Например, регулярное выражение, которое вы даете

(a )+(b )+(c *)c

не соответствует первой записи в вашем результате

a a a b c 

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

"y z a a a b c c z y z a a a b c c z"

Это даст:

a a a b c c
a a b c c
a b c c
a a a b c c
a a b c c
a b c c

Если вы считаете, что позиция не важна, вы должны сделать отчетливый результат.

Тривиальный случай, когда ввод представляет собой пустую строку, должен быть добавлен, если рассматривается потенциальное совпадение.

FYI, это все кандидаты, которые исследует регулярное выражение

"y"
"y "
"y z"
"y z "
"y z a"
"y z a "
"y z a a"
"y z a a "
"y z a a a"
"y z a a a "
"y z a a a b"
"y z a a a b "
"y z a a a b c"
"y z a a a b c "
"y z a a a b c c"
"y z a a a b c c "
"y z a a a b c c z"
" "
" z"
" z "
" z a"
" z a "
" z a a"
" z a a "
" z a a a"
" z a a a "
" z a a a b"
" z a a a b "
" z a a a b c"
" z a a a b c "
" z a a a b c c"
" z a a a b c c "
" z a a a b c c z"
"z"
"z "
"z a"
"z a "
"z a a"
"z a a "
"z a a a"
"z a a a "
"z a a a b"
"z a a a b "
"z a a a b c"
"z a a a b c "
"z a a a b c c"
"z a a a b c c "
"z a a a b c c z"
" "
" a"
" a "
" a a"
" a a "
" a a a"
" a a a "
" a a a b"
" a a a b "
" a a a b c"
" a a a b c "
" a a a b c c"
" a a a b c c "
" a a a b c c z"
"a"
"a "
"a a"
"a a "
"a a a"
"a a a "
"a a a b"
"a a a b "
"a a a b c"
"a a a b c "
"a a a b c c"
"a a a b c c "
"a a a b c c z"
" "
" a"
" a "
" a a"
" a a "
" a a b"
" a a b "
" a a b c"
" a a b c "
" a a b c c"
" a a b c c "
" a a b c c z"
"a"
"a "
"a a"
"a a "
"a a b"
"a a b "
"a a b c"
"a a b c "
"a a b c c"
"a a b c c "
"a a b c c z"
" "
" a"
" a "
" a b"
" a b "
" a b c"
" a b c "
" a b c c"
" a b c c "
" a b c c z"
"a"
"a "
"a b"
"a b "
"a b c"
"a b c "
"a b c c"
"a b c c "
"a b c c z"
" "
" b"
" b "
" b c"
" b c "
" b c c"
" b c c "
" b c c z"
"b"
"b "
"b c"
"b c "
"b c c"
"b c c "
"b c c z"
" "
" c"
" c "
" c c"
" c c "
" c c z"
"c"
"c "
"c c"
"c c "
"c c z"
" "
" c"
" c "
" c z"
"c"
"c "
"c z"
" "
" z"
"z"

Также хорошо знать, как работают 2 основных типа регулярных выражений (NFA и DFA)

из http://msdn.microsoft.com/en-us/library/e347654k.aspx

.NET(и JAVA тоже, я думаю), являются двигателями регулярного выражения NFA (в отличие от DFA) и поскольку он обрабатывает конкретный элемент языка, двигатель использует жадное совпадение; то есть он совпадает с той же строкой входной строки, что и возможно, может. Но он также сохраняет свое состояние после успешного сопоставления подвыражение. Если совпадение в конечном итоге не удастся, двигатель может вернуться к сохраненное состояние, чтобы он мог попробовать дополнительные совпадения. Этот процесс отказаться от успешного подвыражения, чтобы более поздний язык элементы в регулярном выражении также могут совпадать, известно как возвраты.

Ответ 5

Учитывая эти очень специфические ограничения (т.е. это не общее решение), это будет работать:

import java.util.Set;
import java.util.TreeSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class test {

    public static void main(String[] args) {

        String s = "y z a a a b c c z";

        Pattern p = Pattern.compile("(a )+(b )+(c ?)+");
        Set<String> set = recurse(s, p, 0);
    }

    public static Set<String> recurse(String s, Pattern p, int depth) {
        int temp = depth;
        while(temp>0) {
            System.out.print("  ");
            temp--;
        }
        System.out.println("-> " +s);

        Matcher matcher = p.matcher(s);
        Set<String> set = new TreeSet<String>();

        if(matcher.find()) {
            String found = matcher.group().trim();
            set.add(found);
            set.addAll(recurse(found.substring(1), p, depth+1));
            set.addAll(recurse(found.substring(0, found.length()-1), p, depth+1));
        }

        while(depth>0) {
            System.out.print("  ");
            depth--;
        }
        System.out.println("<- " +s);
        return set;
    }
}

Я уверен, что вы можете приспособить его для работы в других случаях, но рекурсия в согласованную строку означает, что совпадающие совпадения (например, то, что указано в @ahenderson) не будут работать.