इनपुट

Question

से न्यूनतम नियमित अभिव्यक्ति प्राप्त करें मेरे पास एक दूरस्थ "एजेंट" है जो स्ट्रिंग को सौंपने पर "हां" या "नहीं" देता है। इस एजेंट के साथ संचार करना महंगा है, इसलिए मैं एक पुस्तकालय ढूंढने की उम्मीद कर रहा हूं जो मुझे इसके निर्माण के बारे में बुद्धिमान होने के दौरान सकारात्मक और नकारात्मक प्रतिक्रिया देने के लिए नियमित रूप से नियमित अभिव्यक्ति बनाने की अनुमति देगा। यह मुझे भेजने के पक्ष में जवाब कैश करने की अनुमति देगा।

उदाहरण के लिए, मान लीजिए कि हम एजेंट को "अच्छा" से पूछते हैं और "हां" प्राप्त करते हैं। प्रारंभिक व्युत्पन्न नियमित अभिव्यक्ति "अच्छा" होना चाहिए।

मान लीजिए कि मैं "goop" के साथ क्वेरी करता हूं और "हां" प्राप्त करता हूं। मैं व्युत्पन्न नियमित अभिव्यक्ति "goo [dp]" होने की अपेक्षा करता हूं, न कि "अच्छा | goop"।

और आगे।

मुझे अपने व्युत्पन्न रेगेक्स में बैकट्रैकिंग या किसी अन्य फैंसी गैर-रैखिक समय संचालन की आवश्यकता नहीं है। संभावित रूप से उत्पन्न रेगेक्स हुड के नीचे एक डीएफए होगा। क्या किसी को यह करने में सक्षम किसी भी सी/सी ++ नियमित अभिव्यक्ति पुस्तकालयों के बारे में पता है? वैकल्पिक रूप से, कारण यह एक बेवकूफ विचार है और मेरी असली समस्या के बेहतर समाधान भी उपयोगी होंगे।

Answer 1

ठीक है, जब तक कि मैं आपकी स्थिति में कुछ याद नहीं कर रहा हूं, मुझे लगता है कि स्मृति एक गूंगा कैश को लागू करने के लिए पर्याप्त सस्ता है - कहें, <std::string, bool> का एक unordered_map। न केवल निर्माण करना बहुत आसान होगा, यह संभवतः तेज़ भी होगा, क्योंकि आप हैश मानचित्र बना रहे हैं। इसका एकमात्र नकारात्मक पक्ष यह है कि यदि आप रिजर्व सेवा को एक बज़िलियन अलग-अलग कुंजियों से पूछने जा रहे थे, तो यह सबसे अच्छा तरीका नहीं हो सकता है।

Answer 2

नियमित अभिव्यक्ति की बजाय, आप Trie का उपयोग कर सकते हैं।

फिर प्रत्येक नई स्ट्रिंग के लिए आप प्रत्येक चरित्र के लिए त्रिभुज एक नोड चलते हैं। मुझे संदेह है कि आप स्ट्रिंग के अंत के लिए मार्कर कैरेक्टर भी चाहते हैं - एक बार जब आप इस चरित्र तक पहुंच जाएंगे, तो नोड मौजूद है, तो इसमें हाँ/कोई जवाब नहीं है।