Java recursivo (?) Repetida (?) Patrón de profundidad (?) Acorde con

Question

estoy tratando de conseguir TODAS las subcadenas de la cadena de entrada que coincide con el patrón dado.

Por ejemplo,

cadena dada: aaxxbbaxb
patrón: un [az] {0,3} b
(Lo que realmente quiero expresar es: todos los patrones que se inicia con una y termina con b, pero puede tener hasta 2 alfabetos en entre ellos)

resultados exactos que quiero (con sus índices):

aaxxb: índice 0 ~ 4
axxb: índice 1 ~ 4
axxbb: el índice 1 ~ 5
axb: Índice 6 ~ 8

Pero cuando lo ejecuto a través de las clases de patrones y Matcher utilizando Pattern.compile() y Matcher.find(), sólo me da:

aaxxb: Índice 0 ~ 4
axb: índice 6 ~ 8

Esta es la pieza de código que he usado.

Pattern pattern = Pattern.compile("a[a-z]{0,3}b", Pattern.CASE_INSENSITIVE); 
Matcher match = pattern.matcher("aaxxbbaxb"); 
while (match.find()) { 
    System.out.println(match.group()); 
} 

¿Cómo se puede recuperar lo cada pieza de cadena que coincide con el patrón?

Por supuesto, no tiene que utilizar las clases Pattern y Matcher, siempre que sea eficiente :)

Answer 1

Una cosa que podría hacer es:

• Crear todas las subcadenas que son posibles 4 caracteres o más (buena suerte con eso Si la cadena es grande)
• Crear un nuevo Matcher para cada una de estas subseries
• hacen un partido() en lugar de un find()
• calcular el desplazamiento absoluto de la subcadena desplazamiento relativo y la información de coincidencias

Answer 2

usted está en efecto la búsqueda de las cuerdas AB, A_B y a__b en una cadena de entrada, donde _ denota una no está en blanco, cuyo valor no te importa

Son tres objetivos de búsqueda. La manera más eficiente en que puedo pensar para hacer esto sería usar un algoritmo de búsqueda como el algoritmo Knuth-Morris-Pratt, con algunas modificaciones. En efecto el pseudocódigo sería algo así como:

for i in 0 to sourcestring.length 
    check sourcestring[i] - is it a? if so, check sourcestring[i+x] 
     // where x is the index of the search string - 1 
    if matches then save i to output list 
    else i = i + searchstring.length 

obviamente, si usted tiene un partido de la posición que debe a continuación, comprobar los caracteres internos de la subcadena para asegurarse de que son alfabético.

ejecutar el algoritmo 3 veces, una para cada término de búsqueda.Sin duda, será mucho más rápido que tratar de hacer la búsqueda usando la coincidencia de patrones.

editar - disculpe, no leí la pregunta correctamente. Si tiene para usar regex, entonces lo anterior no funcionará para usted.

Answer 3

(ver: All overlapping substrings matching a java regex)

Aquí está la solución completa que se me ocurrió. Puede manejar patrones de ancho cero, límites, etc. en la expresión regular original. Examina todas las subcadenas de la cadena de texto y comprueba si la expresión regular coincide solo en la posición específica al rellenar el patrón con el número apropiado de comodines al principio y al final. Parece que funciona para los casos que probé, aunque no he hecho pruebas exhaustivas. Sin duda es menos eficiente de lo que podría ser.

public static void allMatches(String text, String regex) 
    { 
    for (int i = 0; i < text.length(); ++i) { 
     for (int j = i + 1; j <= text.length(); ++j) { 
     String positionSpecificPattern = "((?<=^.{"+i+"})("+regex+")(?=.{"+(text.length() - j)+"}$))"; 
     Matcher m = Pattern.compile(positionSpecificPattern).matcher(text); 

     if (m.find()) 
     { 
      System.out.println("Match found: \"" + (m.group()) + "\" at position [" + i + ", " + j + ")"); 
     } 
     } 
    } 
    }