एक शब्द को देखते हुए यह विलोमपद में तब्दील यह

Question

यहाँ एक बहुत दिलचस्प साक्षात्कार सवाल यह है कि करने के लिए पत्र की न्यूनतम इसके साथ:

एक शब्द को देखते हुए यह करने के लिए पत्र और उनमें कम संलग्न उसे किसी के लिए विलोमपद।

उदाहरण के लिए, यदि "हैलो" स्ट्रिंग दी गई है, तो परिणाम "hellolleh" होना चाहिए। यदि "कोको" दिया जाता है, तो परिणाम "कोकोक" होना चाहिए।

एक दृष्टिकोण जो मैं सोच सकता हूं कि मूल स्ट्रिंग के अंत तक स्ट्रिंग के विपरीत को जोड़ना है, फिर अंत से अतिरिक्त वर्णों को खत्म करने का प्रयास करें। हालांकि, मैं यह समझ नहीं सकता कि यह कुशलतापूर्वक कैसे करें। क्या किसी के पास कोई विचार है?

Answer 1

सबसे पहले पैंडिंड्रोम-नेस के लिए स्ट्रिंग का परीक्षण करने के लिए एक फ़ंक्शन बनाएं, ध्यान रखें कि "ए" और "एए" पालिंड्रोम हैं। वे palindromes हैं, सही ???

इनपुट विलोमपद हैं, तो इसे वापस (0 वर्ण जोड़े जाने की आवश्यकता) लूप एक्स [लंबाई] एक्स [1] की जाँच करने के लिए नीचे से अगर की स्ट्रिंग एक्स सबसेट [i] .. एक्स [लंबाई ] सबसे लंबा पालिंड्रोम खोजने के लिए, एक पालिंड्रोम है।

सबसे लंबे समय तक पैलिंड्रोम से पहले इनपुट स्ट्रिंग से सबस्ट्रिंग लें, इसे उलट दें और इसे अंत में जोड़ने से सबसे कम पैलिंड्रोम को जोड़कर बनाना चाहिए।

कोको => सी + OCO => सी + OCO + स

mmmeep => mmmee + पी => mmmee + p + eemmm

Answer 2

ठीक है! मेरा दूसरा प्रयास यहाँ है।

विचार यह है कि हम यह जानना चाहते हैं कि स्ट्रिंड्रोम को पूरा करने के लिए अतिरिक्त वर्णों को जोड़ते समय स्ट्रिंग के अंत में कितने वर्णों का पुन: उपयोग किया जा सकता है। ऐसा करने के लिए, हम KMP स्ट्रिंग मिलान एल्गोरिदम के एक संशोधन का उपयोग करेंगे। केएमपी का उपयोग करके, हम मूल स्ट्रिंग को इसके विपरीत के लिए खोजते हैं। एक बार जब हम स्ट्रिंग के बहुत अंत तक पहुंच जाएंगे, तो स्ट्रिंग के विपरीत और स्ट्रिंग के अंत में होने वाली मूल स्ट्रिंग के बीच जितना संभव हो उतना मैच होगा। उदाहरण के लिए:

HELLO 
    O 

1010 
010 

3202 
202 

1001 
1001 

इस बिंदु पर, KMP सामान्य रूप से कह सकते हैं कि "कोई मुकाबला नहीं" जब तक मूल स्ट्रिंग विलोमपद था। हालांकि, चूंकि हम वर्तमान में जानते हैं कि स्ट्रिंग का रिवर्स कितना मिलान किया गया था, हम इसके बजाय यह पता लगा सकते हैं कि कितने अक्षर अभी भी गायब हैं और फिर स्ट्रिंग के अंत तक उन्हें ट्रेस करें। पहले मामले में, हम LLEH खो रहे हैं। दूसरे मामले में, हम 1 खो रहे हैं। तीसरे में, हम खो रहे हैं। अंतिम मामले में, हम कुछ भी याद नहीं कर रहे हैं, क्योंकि प्रारंभिक स्ट्रिंग एक पालिंड्रोम है।

इस एल्गोरिदम का रनटाइम एक मानक केएमपी खोज का रनटाइम है और स्ट्रिंग को उलट करने के लिए आवश्यक समय है: ओ (एन) + ओ (एन) = ओ (एन)।

तो अब शुद्धता का बहस करने के लिए। इसे कुछ प्रयास की आवश्यकता होगी। इष्टतम जवाब पर विचार करें:

| original string | | extra characters | 

मान लेते हैं कि हम अंत है, जिसका अर्थ है कि हम मूल स्ट्रिंग के कम से कम रिवर्स पढ़ेंगे से इस पिछड़े पढ़ रहे हैं। इस उलटा स्ट्रिंग का हिस्सा पीछे की ओर मूल स्ट्रिंग के शरीर में फैला हुआ है। वास्तव में, जोड़े गए वर्णों की संख्या को कम करने के लिए, यह वर्णों की सबसे बड़ी संख्या होनी चाहिए जो स्ट्रिंग में वापस आती हैं। हम इसे यहां देख सकते हैं:

| original string | | extra characters | 
      | overlap | 

अब, हमारे केएमपी चरण में क्या होता है? खैर, जब अंदर स्ट्रिंग के विपरीत की तलाश में है, तो केएमपी हर समय जितना संभव हो सके मैच को तब तक रखेगा जब यह स्ट्रिंग में काम करता है। इसका मतलब यह है कि जब केएमपी स्ट्रिंग के अंत को हिट करता है, तो यह मिलान किया गया मिलान वाला हिस्सा सबसे लंबा संभव मैच होगा, क्योंकि केएमपी केवल उम्मीदवार के शुरुआती बिंदु को विफलता पर आगे बढ़ाता है। नतीजतन, हमारे पास यह सबसे लंबा संभव ओवरलैप है, इसलिए हमें अंत में आवश्यक वर्णों की सबसे कम संभव संख्या मिल जाएगी।

मुझे 100% यकीन नहीं है कि यह काम करता है, लेकिन ऐसा लगता है कि हर मामले में मैं इसे फेंक सकता हूं। शुद्धता प्रमाण उचित लगता है, लेकिन यह थोड़ा सा हाथ है क्योंकि औपचारिक केएमपी आधारित सबूत शायद थोड़ा मुश्किल होगा।

आशा है कि इससे मदद मिलती है!

Answer 3

उत्तर देने के लिए मैं इस अनुभवहीन दृष्टिकोण ले जाएगा:

1. जब हमें 0 वर्णों की आवश्यकता है? स्ट्रिंग करते समय यह एक पालिंड्रोम
2. जब हमें 1 वर्ण की आवश्यकता होती है? जब पहली वर्ण स्ट्रिंग को छोड़कर एक पालिंड्रोम
3. है जब हमें 2 वर्णों की आवश्यकता होती है? जब 2 शुरू पात्रों को छोड़कर स्ट्रिंग विलोमपद
4. आदि आदि ...

तो एक एल्गोरिथ्म हो सकता है

for index from 1 to length 
    if string.right(index) is palindrome 
    return string + reverse(string.left(index)) 
    end 
    next 

संपादित

मैं बहुत ज्यादा नहीं एक पायथन लड़का, लेकिन उपरोक्त छद्म कोड का एक सरल दिमागी कार्यान्वयन

>>> def rev(s): return s[::-1] 
... 
>>> def pal(s): return s==rev(s) 
... 
>>> def mpal(s): 
... for i in range(0,len(s)): 
... if pal(s[i:]): return s+rev(s[:i]) 
... 
>>> mpal("cdefedcba") 
'cdefedcbabcdefedc' 
>>> pal(mpal("cdefedcba")) 
True 

हो सकता है

Answer 4

सरल रैखिक समय समाधान।

के हमारे स्ट्रिंग एस

Let च (एक्स, पी) एक्स और पी कंप्यूट च की सबसे लंबी आम उपसर्ग की लंबाई होना कहते हैं (एस [0], राजस्व (एस)), च (एस [1], rev (एस)), ... जहां एस [के] स्थिति के शुरू से एस की प्रत्यय है। जाहिर है, आप न्यूनतम के जैसे कि के + एफ (एस [के], rev (एस)) = लेन (एस) चुनना चाहते हैं। इसका मतलब है कि आपको अंत में के पात्रों को जोड़ना होगा। यदि के 0 है, तो स्टिंग पहले से ही एक पालिंड्रोम है। यदि के = लेन (एस), तो आपको पूरे रिवर्स को जोड़ना होगा।

हमें सभी एस [i] के लिए गणना एफ (एस [i], पी) की आवश्यकता है। यह मुश्किल हिस्सा है। एस का एक प्रत्यय पेड़ बनाएं पेड़ को पार करें और प्रत्येक नोड को पी के साथ सबसे लंबे आम उपसर्ग की लंबाई के साथ अद्यतन करें। पत्तियों पर मूल्य एफ (एस [i], पी) से मेल खाते हैं।