जांचें कि पत्रिका लेख

Question

से वर्णित वर्णों के एक सेट द्वारा दिया गया स्ट्रिंग बनाया जा सकता है, "ध्यान दें कि जब आप एक पत्रिका से एक चरित्र काटते हैं, तो पृष्ठ के विपरीत पक्ष पर वर्ण भी हटा दिया जाता है। एल्गोरिदम दें यह निर्धारित करें कि क्या आप किसी दिए गए पत्रिका से कटआउट पेस्ट करके एक दी गई स्ट्रिंग उत्पन्न कर सकते हैं। मान लीजिए कि आपको एक ऐसा फ़ंक्शन दिया गया है जो किसी भी वर्णित स्थिति के लिए पृष्ठ के विपरीत पक्ष पर चरित्र और इसकी स्थिति की पहचान करेगा। "

मैं यह कैसे कर सकता हूं?

मैं कुछ प्रारंभिक छंटनी कर सकता हूं ताकि अगर किसी आवश्यक चरित्र को उठाए जाने का एक ही तरीका हो, तो प्रारंभ में इसे गतिशील तकनीक के लिए उप-समस्या को बदलने से पहले लिया गया, लेकिन इस प्रारंभिक छंटनी के बाद क्या हुआ?

समय और स्थान जटिलता क्या है?

Answer 1

जैसा कि @LiKao ने सुझाव दिया है, इसे अधिकतम प्रवाह का उपयोग करके हल किया जा सकता है। नेटवर्क बनाने के लिए हम दो "परतें" बनाते हैं: इनपुट स्ट्रिंग में सभी विशिष्ट वर्णों और पृष्ठ पर प्रत्येक स्थिति के साथ एक। एक चरित्र से क्षमता 1 के साथ एक किनारे बनाओ यदि उस स्थिति में उस चरित्र का एक तरफ है। प्रत्येक स्थिति से सिंक तक क्षमता 1 के किनारों को बनाएं, और प्रत्येक स्ट्रिंग को स्रोत से किनारों को इनपुट स्ट्रिंग में उस वर्ण की बहुतायत के बराबर क्षमता के साथ बनाएं।

pos 1 2 3 4 
front F C O Z 
back O O K Z 

हम तो निम्न नेटवर्क उत्पन्न है, क्योंकि यह के किसी भी प्रदान नहीं करता है स्थिति 4 अनदेखी:

उदाहरण के लिए, मान लीजिए कि हम चार पदों के साथ शब्द "foo" एक पृष्ठ पर के लिए खोज रहे हैं आवश्यक पात्र

अब, हम तभी length("FOO") = 3 या उससे अधिक की सिंक करने के लिए स्रोत से एक प्रवाह है निर्धारित करने के लिए की जरूरत है।

Answer 2

आप सीधे गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं।

हमें एन अक्षरों के साथ स्ट्रिंग एस दिया जाता है। हमें टुकड़ों का एक सेट दिया जाता है P = {p_1, ..., p_k}। प्रत्येक टुकड़े के सामने p_i.f में एक अक्षर होता है और पीछे p_i.b में एक होता है।

एफ (जे, पी) फ़ंक्शन के साथ संदर्भित करें जो सत्य लौटाता है यदि यह सबस्ट्रिंग s_1 बनाने के लिए व्यवहार्य है ... s_j p \ subseteq पी में टुकड़ों का उपयोग करके, और अन्यथा गलत है।

निम्नलिखित पुनरावृत्ति है: एफ (एन, पी) = एफ (एन -1, पी-पी_1) | एफ (एन -1, पी-पी_2) | ... | एफ (एन -1, पी-पी_के)

सादे अंग्रेजी में पी में सभी टुकड़ों का उपयोग करने की व्यवहार्यता, substring s_1 की व्यवहार्यता पर निर्भर करता है ... s_n-1 एक कम टुकड़ा दिया जाता है, और हम हटाने का प्रयास करते हैं सभी संभावित टुकड़े (निश्चित रूप से अभ्यास में हमें सभी टुकड़ों को एक-एक करके हटाने की ज़रूरत नहीं है; हमें केवल उन टुकड़ों को हटाने की आवश्यकता है जिनके लिए p_i.f == s_n || p_i.b == s_n)।

प्रारंभिक स्थिति यह है कि एफ (1, पी-पी_1) = एफ (1, पी-पी 2) = ... = सच है, यह मानते हुए कि हमने पहले ही एक प्राथमिकता (रैखिक समय में) की जांच की है कि वहां हैं एस में सभी अक्षरों को कवर करने के लिए पी में पर्याप्त पत्र।