एक स्ट्रिंग * और * इसके उपस्ट्रिंग्स को एक हैस्टैक

में ढूंढें मान लीजिए कि आपके पास स्ट्रिंग है (उदा। needle)। इसके 19 निरंतर सबस्ट्रिंग हैं:एक स्ट्रिंग * और * इसके उपस्ट्रिंग्स को एक हैस्टैक

/(needle|needl|eedle|need|eedl|edle|nee|eed|edl|dle|ne|ee|ed|dl|le|n|e|d|l)/

लेकिन यह वास्तव में नहीं दिखता है:

needle 
needl eedle 
need eedl edle 
nee eed edl dle 
ne ee ed dl le 
n e d l

अगर मैं, एक रेगुलर एक्सप्रेशन से मेल करने के लिए बनाने के लिए एक भूसे के ढेर में, सबस्ट्रिंग के किसी भी मैं बस कर सकता थे सुरुचिपूर्ण। क्या रेगेक्स बनाने का कोई बेहतर तरीका है जो किसी दिए गए स्ट्रिंग के किसी भी सबस्ट्रिंग से लालच से मेल खाता है?

इसके अतिरिक्त, अगर मैंने एक और बाधा उत्पन्न की, तो केवल थ्रेसहोल्ड से अधिक सब्सट्रिंग से मेल खाना चाहता था, उदा।

/(needle|needl|eedle|need|eedl|edle|nee|eed|edl|dle)/

टिप्पणी: कम से कम 3 अक्षरों के सबस्ट्रिंग के लिए मैं जानबूझ कर किसी विशेष regex बोली का उल्लेख नहीं था। कृपया बताएं कि आप किस उत्तर में अपने उत्तर में उपयोग कर रहे हैं।

स्रोत

2012-01-21 CAFxX

यह [सबसे लंबे समय तक सामान्य सबस्ट्रिंग] (http://en.wikipedia.org/wiki/Longest_common_substring_problem) समस्या की तरह दिखता है। क्या इसे regexp होना चाहिए? – dasblinkenlight

सुई की लंबाई निश्चित रूप से घास के मैदान की तुलना में कम परिमाण के आदेश होगी। इसके अलावा, मुझे यह जानने में दिलचस्पी है कि सुई के किसी भी सबस्ट्रिंग की कितनी घटनाएं घाटी में दिखाई देती हैं, न कि एलसीएस कौन सा है। – CAFxX

मुझे नहीं लगता कि घटना बहुत सरल सवाल है (http://stackoverflow.com/questions/9114402/regexp-finding-longest-common-prefix-of-two-strings) में एक regexp का उपयोग करके आसान समाधान है, इसलिए शायद आपको होना चाहिए आपको वास्तव में क्या चाहिए इसकी अधिक विशिष्टता। क्या हम प्रोग्रामिक रूप से regexp उत्पन्न कर सकते हैं? देवताओं को regexp होने की जरूरत है? – gorn

क्या रेगेक्स बनाने का कोई बेहतर तरीका है जो किसी दिए गए स्ट्रिंग के सबस्ट्रिंग से मेल खाता है?

नहीं, लेकिन आप आसानी से ऐसी अभिव्यक्ति उत्पन्न कर सकते हैं।

स्रोत

2012-01-21 17:23:21 Qtax

क्या आपका रेगेक्स 'n (?: ई (?: ई (?: डी (?: एल (?: ई?)?)?)?)?)? 'सबस्ट्रिंग' ई' से मेल खाता है? ऐसा नहीं लगता है कि यह होगा। – CAFxX

यह नहीं होगा, यह पूरी अभिव्यक्ति का एक उदाहरण था जिसमें इनमें से कई शामिल होंगे। – Qtax

फिर यह मेरे समाधान से भी कम सुरुचिपूर्ण है, है ना? – CAFxX

रूप Qtax का सुझाव दिया, अभिव्यक्ति

n(e(e(d(l(e)?)?)?)?)?|e(e(d(l(e)?)?)?)?|e(d(l(e)?)?)?|d(l(e)?)?|l(e)?|e

यदि आप एक स्पष्ट नियमित अभिव्यक्ति लिखने के लिए (egrep वाक्य रचना, वैकल्पिक रूप से (?:...) द्वारा (...) की जगह) चाहता था जाने का रास्ता होगा। प्रारंभिक समाधान की तुलना में यह बेहतर क्यों है कि संघीय संस्करण को मूल संस्करण में ओ (एन^3) स्पेस की तुलना में केवल ओ (एन^2) स्पेस की आवश्यकता होती है, जहां n इनपुट की लंबाई है। अंतर देखने के लिए इनपुट के रूप में extraordinarily के साथ इसे आज़माएं। मुझे लगता है कि संघीय संस्करण भी कई regexp इंजनों के साथ तेजी से है।

अभिव्यक्ति

nee(d(l(e)?)?)?|eed(l(e)?)?|edl(e)?|dle

लंबाई 3 या उससे अधिक समय के सबस्ट्रिंग के लिए दिखेगा।

जैसा कि vhallac द्वारा इंगित किया गया है, उत्पन्न नियमित अभिव्यक्ति थोड़ा अनावश्यक हैं और इसे अनुकूलित किया जा सकता है। प्रस्तावित Emacs उपकरण के अलावा, एक पर्ल पैकेज Regexp::Optimizer है जो मुझे उम्मीद है कि यहां मदद मिलेगी, लेकिन पहली नियमित अभिव्यक्ति के लिए त्वरित जांच विफल रही।

ध्यान दें कि कई regexp इंजन डिफ़ॉल्ट रूप से गैर-ओवरलैपिंग खोज करते हैं। अपनी समस्या की आवश्यकताओं के साथ इसे जांचें।

स्रोत

2012-01-30 21:57:37 krlmlr

क्या यह लाइब्रेरी में बंडल किया गया है Emacs के बाहर से इस्तेमाल किया जा सकता है? – krlmlr

ओह। मैं कुछ '?: दूसरे को हटाने के लिए भूल गया: '(dle | e (dle? | Ed (le?)?) | Nee (d (le?)?)?)' – vhallac

-2

शायद आप बस के लिए .*(.{1,6}).*

स्रोत

2012-02-01 18:04:59 mtanti

पीएस मुझे नहीं पता कि आपने डुप्लिकेट उप- तार। इसमें उन्हें शामिल किया जाएगा ताकि आपको प्रोग्राम की दृष्टि से देखभाल करनी पड़े, उदाहरण के लिए हैश सेट का उपयोग करके। – mtanti

यह * कुछ * * से मेल खाएगा ... मुझे नहीं लगता कि आपका उत्तर मेरे प्रश्न से कैसे संबंधित है ... – CAFxX

यह स्ट्रिंग में सभी उप-तारों से मेल खाएगा। या मैं आपको सही ढंग से समझ नहीं रहा हूँ? – mtanti

देख रहे हैं मैं सुरुचिपूर्ण almostsolution, निर्भर करता है कितनी बुरी तरह से आप केवल एक regexp की जरूरत मिल गया है।

"$needle\0$heystack" =~ /(.{7}).*?\0.*\1/s

मिलान स्ट्रिंग \ 1 में है: उदाहरण के लिए यहाँ के लिए regexp, जो लंबाई 7 के आम-स्ट्रिंग (पर्ल) पाता है। स्ट्रिंग्स में शून्य चरित्र नहीं होना चाहिए जिसे विभाजक के रूप में उपयोग किया जाता है।

आपको एक चक्र बनाना चाहिए जो सुई की लंबाई के साथ स्टार्टर्स और ट्रेसहोल्ड तक चला जाता है और regexp से मिलान करने का प्रयास करता है।

स्रोत

2012-02-02 17:47:10 gorn

सुरुचिपूर्ण! रन टाइम के बारे में कैसे? – krlmlr

वास्तव में सुरुचिपूर्ण! – CAFxX

बहुत प्रभावशाली। एक सवाल, हालांकि: यह "ईई एड" (या अपने घास के मैदान में लगातार सामान्य रूप से छोटे तारों) से मेल नहीं खाता है? – vhallac

एक स्ट्रिंग * और * इसके उपस्ट्रिंग्स को एक हैस्टैक

उत्तर

संबंधित मुद्दे