Alle überlappenden Teilstrings entsprechen einem Java-Regex

Question

Gibt es eine API-Methode, die alle (möglicherweise überlappenden) Teilstrings zurückgibt, die einem regulären Ausdruck entsprechen?

Zum Beispiel habe ich eine Textzeichenfolge: String t = 04/31 412-555-1235;, und ich habe ein Muster: Pattern p = new Pattern("\\d\\d+");, die Zeichenfolgen aus zwei oder mehr Zeichen entspricht.

Die Spiele ich sind: 04, 31, 412, 555, 1235

Wie kann ich überlappende Matches bekommen?

Ich mag der Code zurück: 04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35.

Theoretisch sollte es möglich sein - Es gibt einen offensichtlichen O(n^2) Algorithmus, der alle Teilstrings gegen das Muster auflistet und überprüft.

EDIT

vielmehr alle Substrings als aufzählt, ist es sicherer, die region(int start, int end) Methode in Matcher zu verwenden. Das Überprüfen des Musters gegen einen separaten extrahierten Teilstring kann das Ergebnis der Übereinstimmung ändern (z. B. wenn am Anfang/Ende des Musters eine nicht erfassende Gruppen- oder Wortgrenzenprüfung stattfindet).

EDIT 2

Eigentlich ist es unklar, ob region() tut, was Sie für Null-Breite Matches erwarten. Die Spezifikation ist vage, und Experimente liefern enttäuschende Ergebnisse.

Zum Beispiel:

String line = "xx90xx"; 
String pat = "\\b90\\b"; 
System.out.println(Pattern.compile(pat).matcher(line).find()); // prints false 
for (int i = 0; i < line.length(); ++i) { 
    for (int j = i + 1; j <= line.length(); ++j) { 
    Matcher m = Pattern.compile(pat).matcher(line).region(i, j); 
    if (m.find() && m.group().size == (j - i)) { 
     System.out.println(m.group() + " (" + i + ", " + j + ")"); // prints 90 (2, 4) 
    } 
    } 
} 

Ich bin mir nicht sicher, was die eleganteste Lösung ist. Ein Ansatz wäre, einen Teilstring von line zu nehmen und mit den entsprechenden Begrenzungszeichen zu füllen, bevor überprüft wird, ob der pat übereinstimmt.

EDIT 3

Hier ist die vollständige Lösung, die ich mit aufkommen. Es kann Muster mit Nullbreite, Grenzen usw. im ursprünglichen regulären Ausdruck behandeln. Es durchsucht alle Teilzeichenfolgen der Textzeichenfolge und überprüft, ob der reguläre Ausdruck nur an der bestimmten Position übereinstimmt, indem das Muster mit der entsprechenden Anzahl von Platzhaltern am Anfang und Ende aufgefüllt wird. Es scheint für die Fälle zu funktionieren, die ich ausprobiert habe - obwohl ich noch nicht ausführlich getestet habe. Es ist sicherlich weniger effizient als es sein könnte.

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 + ")"); 
     } 
     } 
    } 
    } 

EDIT 4

Hier ist ein besserer Weg, dies zu tun: https://stackoverflow.com/a/11372670/244526

EDIT 5

Die JRegex Bibliothek unterstützt alle überlappende Teil der Suche nach einem java regex passend (obwohl es scheint, seit einer Weile nicht aktualisiert worden zu sein).Insbesondere gibt die documentation on non-breaking search:

Mit non-breaking Suche können Sie alle möglichen occureneces eines Muster zu finden, einschließlich derer, die sich schneiden oder verschachtelt. Dies ist erreicht mit der Matcher-Methode fortfahren() statt find()

Answer 1

Das nächste, was Sie bekommen können, ist etwas ähnliches.

"(?=((\\d*)\\d))(?=(\\d)\\d*)" 

Das Ergebnis wird in 1 die Erfassung seine Gruppe, 2 und 3

Soweit meine Phantasie gehen kann, kann ich nur als ein gangbaren Weg für den Fang in der Länge Null Behauptung denkt, die wieder zu erlangen gleiche Position einer Zeichenfolge. Das Erfassen von Text außerhalb der Assertion der Länge Null wird den Text ein für allemal konsumieren (Look-Behind kann nur die Länge fester Länge in Java erfassen, so dass es als unzugänglich angesehen werden kann).

Diese Lösung ist nicht perfekt: abgesehen von der Wiederholung (von Text an der gleichen Position!) Und leeren String-Übereinstimmungen werden nicht alle möglichen Teilstrings erfasst.

Eine Möglichkeit, alle möglichen Teil zu erfassen ist die folgende Regex mit dem Wert von n ab 1 konstruieren:

"(?=(\\d{" + n + "}))" 

und passen Sie die Saite gegen diese zum Erhöhen von n bis es keine Übereinstimmung gibt.

Diese Methode ist natürlich ineffizient im Vergleich zu der Methode, alle Zahlen mit "\ d +" zu vergleichen und alle Teilzeichenfolgen zu extrahieren.

Answer 2

Es ist machbar als O (n)nur, wenn Sie den Bereich der erlaubten Anzahl Länge angeben.

Sagen sie 2 bis 4 Ziffern (Nummern 00-9999): (?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)

Dies ist eine Null-Länge Behauptung über positive Vorschau, wie Look-Ahead in Gruppen zu erfassen. Das Ergebnis ist ein Array aller 2-4-stelligen Strings, die innerhalb der Regex-Eingabe gefunden werden können, zusammen mit Duplikaten und leeren Strings (für nicht übereinstimmende Captures).

Ich bin kein Java-Entwickler, aber ich glaube, ein Perl-Skript kann auch als Beispiel gelesen werden.

#!/usr/bin/perl          # perl script 
use List::MoreUtils qw/ uniq /;      # uniq subroutine library 
$_ = '04/31 412-555-1235';       # input 
my @n = uniq (/(?=(\d{2}))(?=(\1\d)?)(?=(\2\d)?)/g); # regex (single slash in Perl) 
print "$_\n" for grep(/\S/, @n);      # print non-empty lines 

Der Trick ist, mit Rückreferenzierungen. Wenn Sie eine 2-5-stellige Zeichenfolge erfassen möchten, müssen Sie einen weiteren positiven Lookahead in der Regex verwenden: (?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)(?=(\\3\\d)?).

Ich glaube, das ist ein nächster Ansatz, den Sie machen können. Wenn dies für Sie funktioniert, hinterlassen Sie einen Kommentar und hoffentlich wird ein Java-Entwickler meine Antwort mit Java-Code für das obige Skript bearbeiten.

Answer 3

Ich sah eine ähnliche Situation und ich versuchte die oben genannten Antworten, aber in meinem Fall dauerte es zu viel Zeit durch die Einstellung der Start- und Ende-Index des Matcher aber ich denke, ich habe eine bessere Lösung gefunden, ich bin posten Sie es hier für andere. Also unten ist mein Code-Sniplet.

if (textToParse != null) { 
Matcher matcher = PLACEHOLDER_PATTERN.matcher(textToParse); 
    while(matcher.hitEnd()!=true){ 
     Boolean result = matcher.find(); 
     int count = matcher.groupCount(); 
     System.out.println("Result " +result+" count "+count); 
     if(result==true && count==1){ 
      mergeFieldName = matcher.group(1); 
      mergeFieldNames.add(mergeFieldName); 
      } 
     } 
    } 

Ich habe die Methode matcher.hitEnd() verwendet, um zu überprüfen, ob ich das Ende des Textes erreicht habe.

Hoffe, das hilft. Danke!