Trovare tutte le sottostringhe corrispondenti, non solo il "più esteso" uno

Question

Il codice

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

stampe

a a a b c c 

che è giusto.

ma logicamente, le sottostringhe

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

partita l'espressione regolare troppo.

Così, come posso rendere il codice trovare quelle stringhe troppo, vale a dire non solo il più esteso uno, ma anche i suoi figli ?

Answer 1

È possibile utilizzare reluctant qualifiers come *? e +?. Questi si abbinano il meno possibile, in contrasto con lo standard * e + che sono avidi, cioè corrispondono il più possibile. Tuttavia, questo ti consente solo di trovare "sottotitoli" particolari, non tutti. Un altro controllo può essere ottenuto usando lookahead che controllano i gruppi non catturanti, descritti anche nei documenti. Ma per trovare davvero tutte le sotto-partite, probabilmente dovresti fare da te, cioè costruire l'automa a cui corrisponde la regex e navigare usando un codice personalizzato.

Answer 2

Avrete bisogno di un lazy quantifier.

Si prega di provare la seguente:

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

Si prega inoltre di notare, che ho raggruppato "c" ancora una volta, dal momento che penso che è quello che vuoi. Altrimenti troverete arbitrariamente molti spazi, ma non "c".

Answer 3

L'unico modo in cui riesco a pensare qui sarebbe quello di generare un elenco di tutte le sottostringhe possibili della stringa originale e far corrispondere la regex a ciascuna di esse, conservando quegli elementi in corrispondenza della corrispondenza.

Answer 4

Dati questi vincoli molto specifici (cioè non si tratta di una soluzione generale caso), questo funzionerà:

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

Sono ragionevolmente sicuro che si può adattare a lavorare su altri casi, ma la ricorsione in la stringa abbinata significa che le corrispondenze sovrapposte (come quella indicata da @ahenderson) non funzioneranno.

Answer 5

Non conosco alcun motore regex che possa restituire tutte le corrispondenze valide.

Ma possiamo applicare un po 'di logica per generare tutta la stringa di candidati e presentarla alla regex.

Un candidato viene costruito enumerando tutte le sottostringhe possibili di un dato input.

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

    } 
} 

Questo dà

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

che sembra la risposta corretta, ma contraddice il risultato:

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 

Per esempio, l'espressione regolare che si dà

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

non lo fa corrisponde alla prima voce in il tuo risultato

a a a b c 

La logica sopra può generare corrispondenze identiche se si considera che la posizione di partenza non è importante. Per esempio se è sufficiente ripetere l'input dato un altro tempo:

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

Darà:

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 

Se si considera la posizione non è importante che si dovrebbe fare una netta su questo risultato

Il banale caso in cui l'input è la stringa vuota deve essere aggiunta se è considerata una potenziale corrispondenza.

FYI, questo sono tutti i candidati che l'espressione regolare esamina

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

Inoltre è bene sapere come i 2 tipi principali di regex (NFA e DFA) fanno il loro lavoro

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

.NET (e anche JAVA penso) sono motori regex NFA (in contrapposizione a DFA) e mentre elabora un particolare elemento di linguaggio, il motore utilizza abbinamento avido; vale a dire, corrisponde a gran parte della stringa di input che può contenere . Ma salva anche il suo stato dopo aver corretto con successo una sottoespressione. Se una corrispondenza fallisce, il motore può tornare a uno stato salvato in modo che possa provare altre corrispondenze. Questo processo di che abbandona una corrispondenza di sottoespressione riuscita in modo che anche gli elementi di lingua successiva nell'espressione regolare possano corrispondere è noto come backtracking .