Tüm olası eşleşmeleri nasıl edinilir? Stgex regex

Question

Tüm olası eşleşme eşleşmelerini bulmak istiyorum, bu nasıl mümkün olabilir?

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

çıkışını verir:

0: 2 
1: 2 
2: 25 

Ama tam üçüncü 2: 2 bulamıyorum. Ben aynı anda birkaç belirteçleri aramak için O(n) karmaşıklığı nedeniyle regex kullanmayı tercih ederim.

GÜNCELLEME:

Belki olmayan prefixable listelerine belirteç liste bölmek ve birkaç Regexes oluşturmak? Örneğin: (2|4|25|45|251|455|267) =>(2|4), (25|45|267), (251|455) Bu O(n log(m))

UPDATE gibi bir şeye karmaşıklığı büyüyecek 2:

Lütfen olmayan prefixable vektörlere bölme belirteç vektör kısa STL tabanlı algoritma sağlamak Bu soruyu cevapla.

Answer 1

Bir yineleyici ve tek bir regexp ile mümkün olduğunu düşünmüyorum. İşte nasıl çalışıyor.

Regexp'iniz, "2" veya "25" olan bir alt dizeyi arar. Şimdi, sregex_iterator ile aramaya başlarsınız. Dizenin ilk sembolü ile başlar ve normal ifadenizle eşleşme bulmaya çalışır. Bir eşleşme varsa, "kaydedilir" ve yineleyici maçtan sonra pozisyona ilerletilir. Eşleşme yoksa, yineleyici ileri 1 konum ileriye doğrudur. Bu işlem, dizenin sonuna ulaşılana kadar devam eder.

Şimdi, bir eşleşme bulduğunda, normal ifadenizden en iyi (yani en uzun) eşleşmeyi bulmaya çalışacaktır. Bu nedenle, bir alt öğe hem 2 hem de 25 ile eşleşirse, daha uzun olduğu için 25 alır. Yani 2 düzenli ifadeye ihtiyacınız olduğunu söyleyebilirim.

Answer 2

Üçüncü '2'yi elde edemezsiniz, çünkü normal ifadeler her zaman en uzun eşleşmeyi döndürür. "Tüm olası eşleşmeleri" elde edebilmek için sorguyu iki kez çalıştırmanız gerekir, çünkü 2 tanesi 25'inde yer almaktadır.