2015-10-15 5 views
8

Mi piacerebbe trovare tutte le possibili corrispondenze di regex, come è possibile?Come ottenere tutte le possibili corrispondenze di std :: regex

regex rx("(2|25)"); 
string s = "2225"; 
for (sregex_iterator it(s.begin(), s.end(), rx), end; it != end; ++it) { 
    cout << it->position() << ": " << it->str() << endl; 
} 

Dà uscita:

0: 2 
1: 2 
2: 25 

ma non trova terzo 2: 2 esattamente. Preferisco usare regex a causa della complessità O(n) per la ricerca di più token contemporaneamente.

UPDATE:

Forse divisi lista di token per le liste non prefixable e creare più espressioni regolari? Ad esempio: (2|4|25|45|251|455|267) =>(2|4), (25|45|267), (251|455) Questa crescerà la complessità a qualcosa di simile O(n log(m))

UPDATE 2:

prega, di fornire a breve algoritmo di STL a base di scissione vettore token per i vettori non prefixable a rispondi a questa domanda.

+0

Se si desidera avere corrispondenze solo su '2', perché si usa' | 25' come parte di la tua espressione regolare? – Phylogenesis

+0

@Phylogenesis Voglio scoprire tutte le 4 corrispondenze per 'O (n)' complessità :) – k06a

+0

Credo che non si possa eguagliare lo stesso personaggio in due gruppi di corrispondenza diversi (ad esempio non sarà possibile abbinare il '2' come parte di '25' ma anche da solo). – Phylogenesis

risposta

2

Non penso sia possibile con un iteratore e una singola espressione regexp. Ecco come funziona.

Il tuo regexp cerca una sottostringa che sia "2" o "25". A questo punto, inizi la ricerca con sregex_iterator. Inizia con il primo simbolo della stringa e cerca di trovare la corrispondenza con la tua espressione regolare. Se c'è una corrispondenza, è "registrata" e l'iteratore è avanzato nella posizione dopo la partita. Se non c'è corrispondenza, l'iteratore viene avanzato di 1 posizione in avanti. Questo processo continua fino al raggiungimento della fine della stringa.

Ora, ogni volta che trova una corrispondenza cercherà di trovare la migliore (cioè la più lunga) corrispondenza dalla tua espressione regolare. Quindi se una sottostringa corrisponde sia a 2 sia a 25, sarà necessario lo 25 poiché è più lungo. Quindi direi che hai bisogno di 2 espressioni regolari.

+0

Aiutami ad evitare l'espressione regolare 'm', ognuno conterrà solo 1 token :) La complessità cresce a' O (nm) ':( – k06a

+1

Non penso che corrisponda effettivamente la partita più lunga, corrisponde alla prima * partita * L'ordine dei sostituti è importante: vedi questo [esempio] (http://ideone.com/Jgq9pZ). – Phylogenesis

+0

@Phylogenesis, è affascinante perché sulla mia macchina il risultato è esattamente l'opposto ('rx1' trova' 2 2 25' e 'rx2' trova' 2 2 2') – SingerOfTheFall

1

Non è possibile ottenere il terzo '2', perché le regex restituiscono sempre la corrispondenza più lunga. Per ottenere "tutte le possibili corrispondenze" è necessario eseguire la query due volte, poiché 2 è contenuta in 25.