Encontrar todas las subcadenas coincidentes, no sólo el "más extendida" uno

Question

El código

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

impresiones

a a a b c c 

que es correcto.

pero lógicamente, las subseries

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

partido de la expresión regular también.

Así que, ¿cómo puedo hacer que el código encontrar esas subseries también, es decir, no sólo la más extendida uno, sino también sus hijos ?

Answer 1

Puede usar el reluctant qualifiers como *? y +?. Estos coinciden lo menos posible, a diferencia del estándar * y + que son codiciosos, es decir, coinciden tanto como sea posible. Aún así, esto solo le permite encontrar "sub-matches" particulares, no todos. Se puede lograr un poco más de control utilizando el control anticipado de grupos no capturadores, también descrito en los documentos. Pero para encontrar realmente todas las subclases, probablemente tendrías que hacer las cosas tú mismo, es decir, construir el autómata al que corresponda la expresión regular y navegar por él utilizando un código personalizado.

Answer 2

Necesitará un lazy quantifier.

Por favor, intente lo siguiente:

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

También note por favor, que Agrupé "c" una vez más, ya que creo que es lo que quieres. De lo contrario, encontraría arbitrariamente muchos espacios, pero no "c".

Answer 3

La única manera que se me ocurre en este caso sería para generar una lista de todas las posibles subcadenas de la cadena original y que coincida con la expresión regular contra cada uno de ellos, conservando los mismos, cuando se igualaron.

Answer 4

Dadas estas restricciones muy específicas (es decir, esto no es una solución general caso), esto va a funcionar:

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

Estoy razonablemente seguro se puede adaptar para trabajar en otros casos, pero la recursividad en la cadena coincidente significa que las coincidencias superpuestas (como la señalada por @ahenderson) no funcionarán.

Answer 5

No conozco ningún motor de expresiones regulares que pueda devolver todas las coincidencias válidas.

Pero podemos aplicar un poco de lógica para generar toda la cadena candidatos y presentarlo a la expresión regular.

Un candidato se construye mediante la enumeración de todos los posibles subcadena de una entrada dada.

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

    } 
} 

Esto da

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

que parece la respuesta correcta, pero contradice el resultado:

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 

Por ejemplo, la expresión regular que le dan

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

no lo hace coincide con la primera entrada en su resultado

a a a b c 

La lógica anterior puede generar coincidencias idénticas si considera que la posición inicial no es importante. Por ejemplo, si sólo tiene que repetir la entrada dada en otra ocasión:

"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 

Si se tiene en cuenta la posición no es importante que debe hacer una clara en este resultado

El trivial El caso donde la entrada es la cadena vacía también se debe agregar si se considera una coincidencia potencial.

FYI, esto son todos los candidatos que la expresión regular examina

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

También es bueno saber cómo los 2 tipos principales de expresiones regulares (NFA y DFA) hacen su trabajo

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

.NET (y JAVA también, creo) son motores de expresiones regulares NFA (en oposición a DFA) y como procesa un elemento de idioma particular, el motor usa concordancia codiciosa; es decir, coincide con la mayor cantidad posible de la cadena de entrada como . Pero también guarda su estado después de hacer coincidir una subexpresión. Si una coincidencia falla finalmente, el motor puede volver a un estado guardado para que pueda probar coincidencias adicionales. Este proceso de abandonando una coincidencia de subexpresión exitosa para que los elementos posteriores del lenguaje en la expresión regular también puedan coincidir se conoce como retroceso.