संख्याओं को छोड़ने के लिए एल्गोरिदम

Question

आपको एक पूर्णांक एन दिया जाता है जो लंबे समय तक फिट बैठता है (2^63-1 से कम) और 50 अन्य पूर्णांक। आपका काम यह पता लगाने के लिए है कि 1 से एन तक कितनी संख्या में 50 नंबरों में से कोई भी इसके सबस्ट्रिंग के रूप में नहीं है?

यह प्रश्न एक साक्षात्कार से है।

Answer 1

आपने आधार निर्दिष्ट नहीं किया है, लेकिन मैं सामान्यता के नुकसान के बिना दशमलव मानूंगा।

सबसे पहले, यह मान लें कि यह एक स्ट्रिंग समस्या है, न कि संख्यात्मक।

अन्य तारों के सबस्ट्रिंग के रूप में 50 पूर्णांक को पहचानने के लिए एक सीमित automaton ए बनाएं। जैसे, दो पूर्णांकों 44 और 3 रे

^.*(44|3).*$ 

एक परिमित automaton बी बिल्ड सभी नंबरों को कम से कम एन पहचान करने के लिए से सबस्ट्रिंग के रूप में पहचाने जाते हैं। उदाहरण के लिए, दशमलव में 1 के माध्यम से 27 (सम्मिलित) पहचान करने के लिए, कि प्राप्त किया जा सकता आरई

^([1-9]|1[0-9]|2[0-7])$ 

कंप्यूट चौराहे सी ऑटोमेटा एक और बी है, जो बारी एक में है की संकलन के द्वारा एफए।

सी द्वारा मान्यता प्राप्त भाषा के आकार की गणना करने के लिए गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग करें। ए द्वारा मान्यता प्राप्त भाषा के आकार से, उसी एल्गोरिदम द्वारा गणना की गई घटाएं।

(मैं दावा कर रहा हूँ नहीं है कि इस asymptotically इष्टतम है, लेकिन यह एक काफी तेजी से परियोजना यूलर समस्याओं :)

Answer 2

यह केवल क्या पहले से ही लिखा था larsmans का एक विवरण है की बहुत सारी हल करने के लिए किया गया था। अगर आपको यह जवाब पसंद है, तो कृपया उसे अतिरिक्त वोट दें।

एक परिमित automaton, एफए, बस राज्यों, और नियमों का एक सेट कह रही है कि अगर आप राज्य S में हैं और अगले वर्ण आप खिलाया हैं c है तो आप राज्य T के लिए संक्रमण है। दो राज्य विशेष हैं। एक मतलब है, "यहां शुरू करें" और दूसरे माध्यम "मैं सफलतापूर्वक मेल खाता हूं"। पात्रों में से एक विशेष है, और इसका मतलब है "स्ट्रिंग अभी समाप्त हो गई"। तो आप एक स्ट्रिंग और एक सीमित automaton लेते हैं, प्रारंभिक स्थिति में शुरू करते हैं, मशीनों को बदलने और राज्यों को बदलते रहते हैं। यदि आप कोई राज्य अप्रत्याशित इनपुट देते हैं तो आप मिलान करने में विफल रहते हैं। यदि आप कभी भी "मैं सफलतापूर्वक मेल खाता हूं" राज्य तक पहुंचने पर आप मिलान करने में सफल होते हैं।

अब एक नियमित अभिव्यक्ति को एक सीमित स्वचालित रूप से परिवर्तित करने के लिए एक प्रसिद्ध एल्गोरिदम है जो स्ट्रिंग से मेल खाता है और केवल तभी होता है जब वह नियमित अभिव्यक्ति मेल खाती हो। (यदि आपने नियमित अभिव्यक्तियों के बारे में पढ़ा है, तो डीएफए इंजन कैसे काम करते हैं।) उदाहरण के लिए मैं पैटर्न ^.*(44|3).*$ का उपयोग करूंगा जिसका अर्थ है "स्ट्रिंग की शुरुआत, किसी भी संख्या में वर्ण, 44 या 3 के बाद, किसी के बाद स्ट्रिंग के अंत के बाद वर्णों की संख्या।"

पहले आइए लेबल पदों के सभी हम जब हम अगले चरित्र के लिए देख रहे नियमित अभिव्यक्ति में में हो सकता है: ^ एक .*(4 बी 4|3) सी .*$

हमारे नियमित अभिव्यक्ति इंजन के राज्यों हो जाएगा उन पदों के सबसेट, और विशेष राज्य मिलान। राज्य संक्रमण का नतीजा उन राज्यों का सेट होगा जो हम उस स्थिति में थे, और एक विशेष चरित्र देखा। हमारी प्रारंभिक स्थिति आरई की शुरुआत में है , जो {ए} है। यहां राज्य हैं जिन्हें पहुंचा जा सकता है:

S1: {A} # start 
S2: {A, B} 
S3: {A, C} 
S4: {A, B, C} 
S5: matched 

यहाँ संक्रमण नियम हैं:

S1: 
    3: S3 
    4: S2 
    end of string: FAIL 
    any other char: S1 
S2: 
    3: S3 
    4: S3 
    end of string: FAIL 
    any other char: S1 
S3: 
    4: S4 
    end of string: S5 (match) 
    any other char: S3 
S4: 
    end of string: S5 (match) 
    any other char: S4 

अब अगर आप किसी भी स्ट्रिंग ले, शुरू राज्य S1 में है, और नियमों का पालन करें, तो आप उस पैटर्न की भरपाई करेंगे। प्रक्रिया लंबी और थकाऊ हो सकती है, लेकिन सौभाग्य से स्वचालित हो सकती है। मेरा अनुमान है कि लार्सन ने इसे अपने इस्तेमाल के लिए स्वचालित कर दिया है। (तकनीकी नोट, "आरईएस में पदों" से "उन पदों के सेट" में विस्तार जो आप संभवतः हो सकते हैं "या तो आगे या यहां चलने पर किया जा सकता है। अधिकांश आरईएस के लिए इसे आगे करना बेहतर है , यहां पर। लेकिन पैथोलॉजिकल उदाहरणों का एक छोटा सा हिस्सा राज्यों की एक बड़ी संख्या के साथ हवादार हो जाएगा, और रन-टाइम पर ऐसा करना बेहतर हो सकता है।)

हम इसे किसी भी नियमित अभिव्यक्ति के साथ कर सकते हैं। उदाहरण के लिए ^([1-9]|1[0-9]|2[0-7])$ लेबल प्राप्त कर सकते हैं: ^ एक ([1-9]|1 बी [0-9]|2 सी [0-7]) डी $ और हम राज्यों मिलती है:

T1: {A} 
T2: {D} 
T3: {B, D} 
T4: {C, D} 

और संक्रमण:

T1: 
    1: T3 
    2: T4 
    3-9: T2 
    any other char: FAIL 
T2: 
    end of string: MATCH 
    any other char: FAIL 
T3: 
    0-9: T2 
    end of string: MATCH 
    any other char: FAIL 
T4: 
    0-7: T2 
    end of string: MATCH 
    any other char: FAIL 

ठीक है, इसलिए हम जानते हैं कि एक रेगुलर एक्सप्रेशन है, क्या एक सीमित automaton, और वे कैसे संबंधित हैं। दो परिमित ऑटोमाटा का चौराहे क्या है? यह सिर्फ एक सीमित automaton है जो मेल खाता है जब दोनों सीमित ऑटोमाटा व्यक्तिगत रूप से मेल खाते हैं, और अन्यथा मिलान करने में विफल रहता है। इसे बनाना आसान है, राज्यों का सेट सिर्फ एक राज्य के जोड़ों का सेट है, और दूसरे में एक राज्य है। इसका संक्रमण नियम प्रत्येक सदस्य के लिए स्वतंत्र रूप से संक्रमण नियम लागू करना है, यदि पूरी तरह से विफल रहता है, तो दोनों मैच दोनों करते हैं।

उपरोक्त जोड़ी के लिए, वास्तव में 13 पर चौराहे निष्पादित करें। हम

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 3 
state: (S3, T2) next char: end of string 
state: (matched, matched) -> matched 

और फिर नंबर 14 पर राज्य (S1, T1) में शुरू करते हैं।

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 4 
state: (S2, T2) next char: end of string 
state: (FAIL, matched) -> FAIL 

अब हम इस पूरे बिंदु पर आते हैं। अंतिम सीमित ऑटोमाटा को देखते हुए, हम यह पता लगाने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं कि इससे कितने तार हैं। यहाँ है कि गणना है:

0 chars: 
    (S1, T1): 1 
    -> (S1, T3): 1 # 1 
    -> (S1, T4): 1 # 2 
    -> (S3, T2): 1 # 3 
    -> (S2, T2): 1 # 4 
    -> (S1, T2): 5 # 5-9 
1 chars: 
    (S1: T2): 5  # dead end 
    (S1, T3): 1 
    -> (S1, T2): 8 # 0-2, 5-9 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S1, T4): 1 
    -> (S1, T2): 6 # 0-2, 5-7 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S2, T2): 1  # dead end 
    (S3, T2): 1 
    -> match: 1 # end of string 
2 chars: 
    (S1, T2): 14  # dead end 
    (S2, T2): 2  # dead end 
    (S3, T2): 2 
    -> match  2 # end of string 
    match: 1 
    -> match  1 # carry through the count 
3 chars: 
    match: 3 

ठीक है, कि काम का एक बहुत कुछ है, लेकिन हमने पाया 3 तार कि एक साथ उन दोनों नियम से मेल देखते हैं कि। और हमने इसे ऐसे तरीके से किया जो बहुत बड़ी संख्या में स्वचालित और स्केल करने योग्य है।

बेशक जिस सवाल को हम मूल रूप से देखते थे वह था कि कितने दूसरे से मेल खाते थे लेकिन पहले नहीं। खैर हम जानते हैं कि दूसरे नियम से 27 मैच, 3 मैच दोनों, इसलिए 24 को दूसरे नियम से मेल खाना चाहिए लेकिन पहले नहीं।

जैसा कि मैंने पहले कहा था, यह सिर्फ लार्समैन समाधान स्पष्ट है। अगर आपने कुछ सीखा, तो उसे ऊपर उठाओ, उसके जवाब के लिए वोट दें। यदि यह सामग्री दिलचस्प लगता है, तो प्रोगोगिंग भाषा व्यावहारिक जैसी पुस्तक खरीदें और परिमित ऑटोमाटा, पार्सिंग, संकलन और इसी तरह के बारे में बहुत कुछ सीखें। यह एक बहुत अच्छा कौशल है, और बहुत से प्रोग्रामर नहीं करते हैं।