Znalezienie wszystkich podciągów pasujące nie tylko „najbardziej rozszerzony” jeden

Question

Kod

String s = "y z a a a b c c z"; 
Pattern p = Pattern.compile("(a)+(b)+(c *)c"); 
Matcher m = p.matcher(s); 
while (m.find()) { 
    System.out.println(m.group()); 
} 

drukuje

a a a b c c 

który ma rację.

Ale Logicznie rzecz biorąc, podciągi

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

mecz regex zbyt.

Tak, jak mogę uczynić kod znaleźć te podciągi zbyt, to znaczy nie tylko najbardziej rozszerzony jeden, ale także jego dzieci?

Answer 1

Można użyć numerów reluctant qualifiers, takich jak *? i +?. Dopasowują się one jak najmniej, w przeciwieństwie do standardowych * i +, które są chciwe, tj. Pasują jak najwięcej. Mimo to pozwala ci to tylko znaleźć konkretne "pod-mecze", nie wszystkie z nich. Pewna większa kontrola może zostać osiągnięta za pomocą kontroli wyprzedzających kontrolujących niezapisywanie grup, również opisanych w dokumentach. Ale aby naprawdę znaleźć wszystkie pod-dopasowania, prawdopodobnie musiałbyś zrobić coś samemu, tj. Zbudować automat, do którego regex odpowiada i nawigować przy użyciu niestandardowego kodu.

Answer 2

Będziesz potrzebować lazy quantifier.

Spróbuj wykonać następujące czynności:

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

Należy również zauważyć, że zgrupowane „c” po raz kolejny, ponieważ myślę, że to, co chcesz. W przeciwnym razie można znaleźć dowolnie wiele spacji, ale nie "c".

Answer 3

Jedyny sposób, jaki mógłbym tu wymyślić, to wygenerowanie listy wszystkich możliwych podłańcuchów oryginalnego łańcucha i dopasowanie wyrażeń regularnych do każdego z nich, zachowując te elementy, w których były dopasowane.

Answer 4

Biorąc pod uwagę te bardzo szczególne ograniczenia (czyli nie jest to rozwiązanie ogólne przypadek), to będzie działać:

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; 
    } 
} 

jestem dość pewien, że można go przystosować do pracy w innych przypadkach, ale rekursji język dopasowany ciąg oznacza, że ​​nakładające się mecze (takie jak wskazany przez @ahenderson) nie będą działać.

Answer 5

Nie znam żadnych silników regex, które mogą przywrócić wszystkie ważne mecze.

Ale możemy zastosować trochę logiki, aby wygenerować wszystkie łańcuchy kandydatów i przedstawić je w regularnym wyliczeniu.

Kandydat jest konstruowany przez wyliczenie całego możliwego podłańcucha danego wejścia.

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(); 
     } 

    } 
} 

Daje

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

który wydaje poprawną odpowiedź, ale zaprzecza swój wynik:

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 

Na przykład, wyrażenie regularne, że dajesz

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

nie dopasuj pierwszy wpis w Twój wynik:

a a a b c 

Powyższa logika może generować identyczne dopasowania, jeśli uznasz, że pozycja początkowa nie jest ważna. Na przykład, jeśli tylko powtarzanie danego wejścia innym razem:

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

To daje:

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 

Jeśli wziąć pod uwagę stanowisko nie ważne należy zrobić wyraźną tego wyniku

trywialne Przypadek, w którym dane wejściowe jest pustym łańcuchem, powinien zostać dodany, jeśli zostanie uznany za potencjalny odpowiednik.

FYI, to są wszyscy kandydaci że regex bada

"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" 

Również dobrze jest wiedzieć, w jaki sposób 2 główne typy regexes (NFA i DFA) wykonywać swoją pracę

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

.NET (i ja też uważam, że JAVA) to silniki regex NFA (w przeciwieństwie do DFA) , a ponieważ przetwarza określony element językowy, silnik używa chciwe dopasowanie; oznacza to, że dopasowuje tyle znaków wejściowych, ile może. Ale zapisuje także swój stan po pomyślnym dopasowaniu podwyrażenia do . Jeśli mecz zakończy się niepowodzeniem, silnik może wrócić do stanu w stanie zapisanym, aby mógł wypróbować dodatkowe dopasowania. Ten proces polegający na rezygnacji z pomyślnego dopasowania podwyrażenia, tak aby późniejszy język mógł się równać z określonymi później wyrażeniami regularnymi, znany jest pod nazwą .