algorithm - मनचेर के एल्गोरिदम(रैखिक समय में सबसे लंबे पैलिंड्रोम सबस्ट्रिंग को खोजने के लिए एल्गोरिदम)




palindrome (6)

मनचेर के एल्गोरिदम को पचाने के लिए लगभग 6-8 घंटे खर्च करने के बाद, मैं तौलिया में फेंकने के लिए तैयार हूं। लेकिन इससे पहले कि, अंधेरे में एक आखिरी शॉट है: क्या कोई इसे समझा सकता है? मुझे कोड की परवाह नहीं है। मैं किसी को एल्गोरिथ्म समझाऊंगा

यहां एक ऐसा स्थान प्रतीत होता है जो दूसरों को एल्गोरिदम समझाते हुए आनंद लेते थे: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

मैं समझता हूं कि आप स्ट्रिंग को क्यों बदलना चाहते हैं, कहें, 'abba' से # a # b # b # a # खो जाने के बाद। उदाहरण के लिए, पहले उल्लिखित वेबसाइट के लेखक का कहना है कि एल्गोरिदम का मुख्य भाग यह है:

                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])

यह गलत लगता है, क्योंकि वह एक बिंदु पर कहता है कि पी [i] 5 बराबर है जब पी [i '] = 7 और पी [i] आर-i के बराबर या बराबर नहीं है।

यदि आप एल्गोरिदम से परिचित नहीं हैं, तो यहां कुछ और लिंक दिए गए हैं: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (मैंने यह कोशिश की है, लेकिन शब्दावली भयानक और भ्रमित है। सबसे पहले, कुछ चीजों को परिभाषित नहीं किया जाता है। इसके अलावा, बहुत सारे चर। आपको यह जानने के लिए एक चेकलिस्ट की आवश्यकता है कि किस चर का संदर्भ है।)

एक और है: http://www.akalin.cx/longest-palindrome-linear-time (शुभकामनाएं)

एल्गोरिदम का मूल आधार रैखिक समय में सबसे लंबा पालिंड्रोम ढूंढना है। यह ओ (एन ^ 2) में न्यूनतम से मध्यम प्रयास के साथ किया जा सकता है। यह एल्गोरिदम इसे ओ (एन) तक पहुंचाने के लिए काफी "चालाक" माना जाता है।


इस साइट पर एल्गोरिदम कुछ बिंदुओं के लिए समझ में आता है http://www.akalin.cx/longest-palindrome-linear-time

इस विशेष दृष्टिकोण को समझने के लिए सबसे अच्छा है कि कागज पर समस्या को हल करने और उन चालों को पकड़ने का प्रयास करें जिन्हें आप प्रत्येक संभावित केंद्र के लिए पैलिंड्रोम की जांच से बचने के लिए लागू कर सकते हैं।

सबसे पहले जवाब दें - जब आपको किसी दिए गए लम्बाई का पालिंड्रोम मिलता है, तो आइए 5 कहें - क्या आप अगले चरण के रूप में नहीं जा सकते हैं, बस इस पैलिंड्रोम के अंत तक कूदें (4 अक्षरों और 4 मध्य अक्षरों को छोड़कर)?

यदि आप लम्बाई 8 के साथ पैलिंड्रोम बनाने की कोशिश करते हैं और लम्बाई> 8 के साथ एक और पैलिंड्रोम रखें, तो कौन सा केंद्र पहले पैलिंड्रोम के दाहिने तरफ है, आपको कुछ मजेदार दिखाई देगा। इसे आज़माएं: लंबाई 8 के साथ पालिंड्रोम - WOWILIKEEKIL - जैसे + ekiL = 8 अब ज्यादातर मामलों में आप केंद्र के रूप में दो ई के बीच जगह और संख्या 8 के रूप में जगह लिखने में सक्षम होंगे और आखिरी एल के बाद कूदने के लिए कूदेंगे बड़े पैलिंड्रोम का केंद्र।

यह दृष्टिकोण सही नहीं है, जो बड़े पैलिंड्रोम का केंद्र ईकीएल के अंदर हो सकता है और यदि आप अंतिम एल के बाद कूदेंगे तो आप इसे याद करेंगे।

LIKE + EKIL खोजने के बाद आप सरणी में 8 डालते हैं कि इन अल्गोस का उपयोग होता है और ऐसा लगता है:

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]

के लिये

[#,वह यह मुझे पसंद है,#]

चाल यह है कि आप पहले से ही जानते हैं कि संभवतया 8 के बाद अगले 7 (8-1) संख्याएं बायीं तरफ समान होंगी, इसलिए अगला चरण स्वचालित रूप से 8 के बाईं ओर 8 से 8 के दाएं से 8 नंबरों की प्रतिलिपि बनाना है दिमाग वे अभी तक अंतिम नहीं हैं। सरणी इस तरह दिखेगी

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] ( हम 8 पर हैं)

के लिये

[#, डब्ल्यू, #, हे, #, डब्ल्यू, #, मैं, #, एल, #, मैं, #, कश्मीर, #, ई, #, ई, #, कश्मीर, #, मैं, #, एल]

आइए एक उदाहरण दें, कि इस तरह की कूद हमारे वर्तमान समाधान को नष्ट कर देगी और देखें कि हम क्या देख सकते हैं।

WOWILIKEEKIL - EKIL के भीतर कहीं भी केंद्र के साथ बड़ा palindrome बनाने की कोशिश करते हैं। लेकिन यह संभव नहीं है - हमें EKIL शब्द को कुछ ऐसा करने की आवश्यकता है जिसमें पैलिंड्रोम हो। क्या? OOOOOh - यह चाल है। हमारे वर्तमान पैलिंड्रोम के दायीं ओर केंद्र के साथ एक बड़ा पालिंड्रोम होने की एकमात्र संभावना यह है कि यह पहले से ही पैलिंड्रोम के दाएं (और बाएं) तरफ है।

चलो WOWILIKEEKIL के आधार पर एक बनाने की कोशिश करते हैं हमें ईकेआईएल को उदाहरण के लिए बड़े पैलिंड्रोम के केंद्र के रूप में ईकेआईके को बदलने की आवश्यकता होगी - जैसे कि किके को भी बदलना याद रखें। हमारे मुश्किल पैलिंड्रोम के पहले अक्षर होंगे:

WOWIKIKEEKIK

जैसा कि पहले कहा गया था - आखिरी बार मैं किकिकेक की तुलना में बड़े पलिंड्रोम का केंद्र बनूंगा:

WOWIKIKEEKIKEEKIKIW

आइए सरणी को हमारे पुराने पैलिंड्रोम पर बनाएं और पता लगाएं कि अतिरिक्त जानकारी का लाभ कैसे प्राप्त करें।

के लिये

[_ डब्ल्यू _ ओ _ डब्ल्यू _ मैं _ के _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

यह [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8 होगा

हम जानते हैं कि अगला I - एक तिहाई सबसे लंबा पैलिंड्रोम होगा, लेकिन चलिए इसे थोड़ा सा भूल जाएं। आइए संख्याओं को सरणी में 8 से दाएं (8 संख्याओं) की प्रतिलिपि बनाने दें

[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]

हमारे लूप में हम ई के बीच नंबर 8 के बीच हैं। मैं (सबसे बड़ा पलिंड्रोम का भविष्य मध्य) के बारे में क्या विशेष हूं कि हम के (सीधे वर्तमान में सबसे बड़ी पलिंड्रोम का अंतिम पत्र) तक नहीं जा सकते हैं? विशेष बात यह है कि यह सरणी के वर्तमान आकार से अधिक है ... कैसे? यदि आप 3 रिक्त स्थान 3 के दाईं ओर ले जाते हैं - तो आप सरणी से बाहर हैं। इसका मतलब यह है कि यह सबसे बड़ा पलिंड्रोम का मध्य हो सकता है और सबसे दूर आप कूद सकते हैं यह पत्र I है।

इस उत्तर की लंबाई के लिए खेद है - मैं algorythm को समझाना चाहता था और आपको आश्वस्त कर सकता हूं - @ ओमनीपोटेंट एंटीटी सही था - मैं आपको समझाए जाने के बाद भी इसे बेहतर समझता हूं :)


पूरा लेख: http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/

सबसे पहले कुछ रोचक गुणों को खोजने के लिए पैलिंड्रोम के साथ बारीकी से निरीक्षण करते हैं। उदाहरण के लिए, एस 1 = "अबाबा" और एस 2 = "अब्बा", दोनों पैलिंड्रोम हैं लेकिन उनके बीच गैर-तुच्छ (यानी लंबाई या वर्ण नहीं) अंतर क्या है? एस 1 एक पालिंड्रोम है जो अदृश्य स्थान के आस-पास केंद्रित है I = 2 और i = 3 (अस्तित्वहीन स्थान!) के बीच। दूसरी ओर एस 2 चरित्र के चारों ओर केंद्रित है i = 2 (यानी सी)। अजीब / यहां तक ​​कि लंबाई के बावजूद एक पालिंड्रोम के केंद्र को दयालु तरीके से संभालने के लिए, वर्णों के बीच विशेष चरित्र $ डालने से पैलिंड्रोम को बदल दें। फिर S1 = "abba" और S2 = "abcba" को t1 = "$ a $ b $ a $ a $ b $ a $" में बदल दिया जाएगा i = 6 और T2 = "$ a $ b $ c $ b पर केंद्रित $ = $ "i = 5 पर केंद्रित। अब, हम देख सकते हैं कि केंद्र मौजूद हैं और लंबाई लगातार 2 * एन + 1 हैं, जहां n = मूल स्ट्रिंग की लंबाई। उदाहरण के लिए,

                    i'          c           i           
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
   T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------

इसके बाद, देखें कि एक (रूपांतरित) palindrome टी की सममित संपत्ति से केंद्र सी के आसपास टी, टी [सीके] = टी [सी + के] 0 के लिए <= k <= c। वह स्थिति सीके और सी + के एक दूसरे के लिए दर्पण हैं। आइए इसे एक और तरीका दें, इंडेक्स सी के दाईं ओर एक इंडेक्स के लिए, दर्पण इंडेक्स i 'सी के बाईं ओर है जैसे कि c-i' = ic => i '= 2 * ci और इसके विपरीत। अर्थात्,

प्रत्येक स्थिति के लिए मैं एक पालिंड्रोमिक सबस्ट्रिंग के केंद्र सी के दाईं ओर, मैं दर्पण की स्थिति है, मैं = 2 * सीआई, और इसके विपरीत।

आइए एक सरणी पी [0..2 * एन] को परिभाषित करें जैसे कि पी [i] i पर केंद्रित पालिंड्रोम की लंबाई के बराबर है। ध्यान दें कि, लंबाई वास्तव में मूल स्ट्रिंग में वर्णों की संख्या द्वारा मापा जाता है (विशेष वर्ण $ को अनदेखा करके)। इसके अलावा न्यूनतम और अधिकतम क्रमशः सी पर केंद्रित एक पालिंड्रोमिक सबस्ट्रिंग की बाएं और दाएं सीमा दें। तो, न्यूनतम = सीपी [सी] और अधिकतम = सी + पी [सी]। उदाहरण के लिए, पैलिंड्रोम एस = "अबाबा" के लिए, रूपांतरित पालिंड्रोम टी, दर्पण केंद्र सी = 6, लंबाई सरणी पी [0..12], न्यूनतम = सीपी [सी] = 6-6 = 0, अधिकतम = सी + पी [सी] = 6 + 6 = 12 और दो नमूना प्रतिबिंबित सूचकांक I और i 'निम्नलिखित चित्र में दिखाए जाते हैं।

      min           i'          c           i           max
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
    T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
      -----------------------------------------------------

इस तरह की लंबाई सरणी पी के साथ, हम पी के अधिकतम तत्व को देखकर सबसे लंबे समय तक पैलिंड्रोमिक सबस्ट्रिंग की लंबाई पा सकते हैं।

पी [i] ट्रांसफॉर्म स्ट्रिंग टी, यानी में केंद्र के साथ एक पालिंड्रोमिक सबस्ट्रिंग की लंबाई है। मूल स्ट्रिंग एस में i / 2 पर केंद्र; इसलिए सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग इंडेक्स से शुरू होने वाली लंबाई पी [i max ] की प्रतिस्थापन होगी (i max -P [i max ]) / 2 जैसे कि अधिकतम अधिकतम पी में पी।

आइए हम अपने गैर-पैलिंड्रोमिक उदाहरण स्ट्रिंग एस = "बाबाबाका" के लिए निम्नलिखित में एक समान चित्र खींचे।

                       min              c               max
                       |----------------|-----------------|
      --------------------------------------------------------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      --------------------------------------------------------------------- 
    T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
      ---------------------------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
      ---------------------------------------------------------------------

सवाल यह है कि पी को कुशलतापूर्वक गणना कैसे करें। सममित संपत्ति निम्नलिखित मामलों का सुझाव देती है कि हम संभावित रूप से पी [i] की गणना करने के लिए बाईं ओर दर्पण सूचकांक I पर पहले गणना किए गए पी [i '] का उपयोग कर उपयोग कर सकते हैं, इसलिए बहुत सारी गणनाएं छोड़ रही हैं। आइए मान लें कि हमारे पास एक संदर्भ पैलिंड्रोम (पहला पालिंड्रोम) है जिसके साथ शुरूआत है।

  1. एक तीसरा पैलिंड्रोम जिसका केंद्र पहले पैलिंड्रोम के दाहिने तरफ के भीतर है, वही लंबाई होगी जो बाएं तरफ दर्पण केंद्र पर लगाए गए दूसरे पैंडिंड्रोम की तरह ही होगी, यदि दूसरा पैलिंड्रोम पहले पैलिंड्रोम की सीमा के भीतर है कम से कम एक चरित्र।
    उदाहरण के लिए सी = 8 पर केंद्रित पहले पालिंड्रोम के साथ निम्नलिखित चित्र में और न्यूनतम = 4 और अधिकतम = 12 से घिरा हुआ तीसरा पालिंड्रोम की लंबाई i = 9 पर केंद्रित है (दर्पण सूचकांक i = 2 * ci = 7 के साथ) है , पी [i] = पी [i '] = 1. ऐसा इसलिए है क्योंकि मैं पर केंद्रित दूसरा पैंडिंड्रोम पहले पैलिंड्रोम की सीमा के भीतर है। इसी तरह, पी [10] = पी [6] = 0।
    
                                          |----3rd----|
                                  |----2nd----|        
                           |-----------1st Palindrome---------|
                           min          i'  c   i           max
                           |------------|---|---|-------------|
          --------------------------------------------------------------------
     idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
          --------------------------------------------------------------------- 
        T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
          ---------------------------------------------------------------------
        P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? |
          ---------------------------------------------------------------------
    
    अब सवाल यह है कि इस मामले की जांच कैसे करें? ध्यान दें, सेगमेंट की सममित संपत्ति लंबाई [min..i '] के कारण खंड [i..max] की लंबाई के बराबर है। साथ ही, ध्यान दें कि दूसरा पैलिंड्रोम पूरी तरह से 1 पैलिंड्रोम के भीतर है यदि आईएफएफ बाएं किनारे के बाएं किनारे पर है, तो पहले पैंडिंड्रोम का मिनट। अर्थात्,
            i'-P[i'] >= min
            =>P[i']-i' &lt -min (negate)
            =>P[i'] &lt i'-min 
            =>P[i'] &lt max-i [(max-i)=(i'-min) due to symmetric property].
    
    1 मामले में सभी तथ्यों का मिश्रण,
    पी [i] = पी [i '], iff (max-i)> पी [i']
  2. यदि दूसरा पैलिंड्रोम पहले पैलिंड्रोम के बाएं बाउंड से परे मिलता है या फैलाता है, तो तीसरा पैलिंड्रोम कम से कम अपने स्वयं के केंद्र से लंबाई को पहले पैलिंड्रोम के दाएं बाहरीतम चरित्र तक रखने की गारंटी देता है। यह लंबाई दूसरे पैलिंड्रोम के केंद्र से पहले पालिंड्रोम के बाएं बाहरीतम चरित्र तक ही है।
    उदाहरण के लिए, निम्नलिखित आकृति में, i = 5 पर केंद्रित दूसरा पैलिंड्रोम पहले पैलिंड्रोम के बाईं ओर फैला हुआ है। तो, इस मामले में हम पी [i] = पी [i '] नहीं कह सकते हैं। लेकिन i = 11 पर केंद्रित तीसरे पैलिंड्रोम की लंबाई, पी [i] कम से कम इसकी केंद्र i = 11 से लंबाई है जो सी पर केंद्रित पहले पैंडिंड्रोम के दाएं बाध्य अधिकतम = 12 है। यही है, पी [i]> = 1। इसका मतलब है कि तीसरा पैलिंड्रोम अधिकतम अधिकतम बढ़ाया जा सकता है अगर केवल तभी होता है जब अगले तत्काल चरित्र प्रतिबिंबित चरित्र के साथ अधिकतम मिलान करता है, और हम इस चेक को आगे बढ़ाते हैं। उदाहरण के लिए, इस मामले में पी [13]! = पी [9] और इसे बढ़ाया नहीं जा सकता है। तो, पी [i] = 1।
                                                        
                  |-------2nd palindrome------|   |----3rd----|---?    
                           |-----------1st Palindrome---------|
                           min  i'          c           i   max
                           |----|-----------|-----------|-----|
          --------------------------------------------------------------------
     idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
          --------------------------------------------------------------------- 
        T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
          ---------------------------------------------------------------------
        P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? |
          ---------------------------------------------------------------------
    
    तो, इस मामले की जांच कैसे करें? यह केवल मामला 1 के लिए असफल चेक है। यही है, दूसरा पालिंड्रोम पहले पालिंड्रोम आईएफएफ के बाएं किनारे का विस्तार करेगा,
            i'-P[i'] &lt min
            =>P[i']-i' >= -min [negate]
            =>P[i'] >= i'-min 
            =>P[i'] >= max-i [(max-i)=(i'-min) due to symmetric property]. 
    
    यही है, पी [i] कम से कम (अधिकतम-i) iff (max-i) पी [i]> = (max-i), iff (max-i) अब, यदि तीसरा पैलिंड्रोम अधिकतम से आगे बढ़ता है तो हमें नए पैलिंड्रोम के केंद्र और सीमा को अद्यतन करने की आवश्यकता है।
    यदि मैं पर केंद्रित पालिंड्रोम पिछले अधिकतम का विस्तार करता है तो हमारे पास नया (विस्तारित) पैलिंड्रोम होता है, इसलिए सी = i पर एक नया केंद्र होता है। नए पैलिंड्रोम की दाएं सीमा तक अधिकतम अपडेट करें।
    1 और मामले 2 के मामले में सभी तथ्यों का मिश्रण, हम एक बहुत ही खूबसूरत छोटे सूत्रों के साथ आ सकते हैं:
            Case 1: P[i] = P[i'],  iff (max-i) > P[i']
            Case 2: P[i]>=(max-i), iff (max-i) = min(P[i'], max-i). 
    
    यही है, पी [i] = मिनट (पी [i '], max-i) जब तीसरा पैलिंड्रोम अधिकतम से अधिक विस्तार योग्य नहीं है। अन्यथा, हमारे पास सी = i और नए अधिकतम = i + P [i] पर केंद्र में नया तीसरा पालिंड्रोम है।
  3. न तो पहला और न ही दूसरा पैलिंड्रोम एक चौथा पालिंड्रोम की पालिंड्रोमिक लंबाई निर्धारित करने में मदद करने के लिए जानकारी प्रदान करता है जिसका केंद्र पहले पैलिंड्रोम के दाहिने तरफ से बाहर है।
    यही है, हम preemptively पी [i] अगर i> अधिकतम निर्धारित नहीं कर सकते हैं। अर्थात्,
    पी [i] = 0, iff max-i <0
    सभी मामलों का संयोजन, हम सूत्रों का निष्कर्ष निकालते हैं:
    पी [i] = अधिकतम> मैं? न्यूनतम (पी [i '], max-i): 0. यदि हम अधिकतम से अधिक विस्तार कर सकते हैं तो हम c = i पर नए केंद्र के संबंध में प्रतिबिंबित वर्ण के साथ अधिकतम वर्णों से मिलान कर सकते हैं। अंत में जब हमारे पास मेल नहीं है तो हम नए अधिकतम = i + P [i] अपडेट करते हैं।

संदर्भ: विकी पेज में एल्गोरिदम विवरण


मैं सहमत हूं कि लिंक की व्याख्या में तर्क बिल्कुल सही नहीं है। मैं नीचे कुछ विवरण देता हूं।

मनचेर का एल्गोरिदम एक टेबल पी में भर जाता है [i] जिसमें मैं विस्तारित करता हूं कि पैंडिंड्रोम कितना दूर रहता है। यदि पी [5] = 3, तो स्थिति पांच के दोनों ओर तीन वर्ण पैलिंड्रोम का हिस्सा हैं। एल्गोरिदम इस तथ्य का लाभ उठाता है कि यदि आपको एक लंबा पालिंड्रोम मिला है, तो आप बाईं ओर पी के मानों को देखकर जल्दी से पैंडिंड्रोम के दाईं ओर पी के मानों को भर सकते हैं, क्योंकि उन्हें अधिकतर होना चाहिए वही।

मैं उस मामले को समझाकर शुरू करूंगा जिसके बारे में आप बात कर रहे थे, और फिर मैं आवश्यकतानुसार इस उत्तर का विस्तार करूंगा।

आर सी पर केंद्रित पालिंड्रोम के दाहिने तरफ के सूचकांक को इंगित करता है। यहां आपके द्वारा इंगित स्थान पर राज्य है:

C=11
R=20
i=15
i'=7
P[i']=7
R-i=5

और तर्क इस तरह है:

if P[i']<=R-i:  // not true
else: // P[i] is at least 5, but may be greater

लिंक में छद्म कोड इंगित करता है कि पी [i] पी [i '] से अधिक या बराबर होना चाहिए यदि परीक्षण विफल रहता है, लेकिन मेरा मानना ​​है कि यह Ri से अधिक या बराबर होना चाहिए, और स्पष्टीकरण उस पर निर्भर करता है।

चूंकि पी [i '] Ri से अधिक है, मैं पर केंद्रित पालिंड्रोम सी पर केंद्रित पालिंड्रोम से पहले फैला हुआ है। हम जानते हैं कि मैं पालिंड्रोम केंद्रित हूं, कम से कम Ri वर्णों का चौड़ा होगा, क्योंकि हमारे पास अभी भी उस बिंदु पर समरूपता है, लेकिन हमें उससे परे स्पष्ट रूप से खोजना है।

यदि पी [मैं] Ri से अधिक नहीं था, तो मैं पर केंद्रित सबसे बड़ा पैलिंड्रोम सी में केंद्रित सबसे बड़ा पालिंड्रोम के भीतर है, इसलिए हम जानते होंगे कि पी [i] पी से बड़ा नहीं हो सकता [i] ']। अगर ऐसा होता, तो हम एक विरोधाभास करेंगे। इसका मतलब यह होगा कि हम पी [i '] से परे मेरे पास केंद्रित पालिंड्रोम का विस्तार करने में सक्षम होंगे, लेकिन अगर हम कर सकते हैं, तो हम समरूपता के कारण' पर केंद्रित पालिंड्रोम भी बढ़ा सकते हैं, लेकिन यह पहले से ही था जितना संभव हो उतना बड़ा होना चाहिए।

यह मामला पहले सचित्र है:

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

इस मामले में, पी [i '] <= Ri। चूंकि हम अभी भी सी में केंद्रित पालिंड्रोम के किनारे से 7 वर्ण दूर हैं, हम जानते हैं कि मेरे आस-पास के कम से कम 7 वर्ण मैं चारों ओर के 7 अक्षरों के समान हैं। चूंकि मैं चारों ओर केवल एक चरित्र पालिंड्रोम था, इसलिए मेरे आस-पास एक चरित्र पैलिंड्रोम भी है।

j_random_hacker ने देखा कि तर्क इस तरह अधिक होना चाहिए:

if P[i']<R-i then
  P[i]=P[i']
else if P[i']>R-i then
  P[i]=R-i
else P[i]=R-i + expansion

यदि पी [i '] <Ri, तो हम जानते हैं कि पी [i] == पी [i'], क्योंकि हम अभी भी सी में केंद्रित पालिंड्रोम के अंदर हैं।

यदि पी [i ']> Ri, तो हम जानते हैं कि पी [i] == Ri, क्योंकि अन्यथा सी पर केंद्रित पालिंड्रोम पिछले आर को बढ़ा दिया होगा।

तो विस्तार वास्तव में केवल विशेष मामले में आवश्यक है जहां पी [i '] == Ri, इसलिए हम नहीं जानते कि पी [i] पर पैलिंड्रोम लंबा हो सकता है या नहीं।

यह पी [i] = min (पी [i '], Ri) और फिर हमेशा विस्तार करके वास्तविक कोड में संभाला जाता है। ऐसा करने का यह तरीका समय जटिलता में वृद्धि नहीं करता है, क्योंकि यदि कोई विस्तार आवश्यक नहीं है, तो विस्तार करने के लिए लिया गया समय निरंतर है।


मैंने एनिमेशन ग्राफिक्स का उपयोग करके इस एल्गोरिदम पर एक वीडियो बनाया। उम्मीद है कि यह आपको समझने में मदद करेगा! https://www.youtube.com/watch?v=kbUiR5YWUpQ


class Palindrome
{
    private int center;
    private int radius;

    public Palindrome(int center, int radius)
    {
        if (radius < 0 || radius > center)
            throw new Exception("Invalid palindrome.");

        this.center = center;
        this.radius = radius;
    }

    public int GetMirror(int index)
    {
        int i = 2 * center - index;

        if (i < 0)
            return 0;

        return i;
    }

    public int GetCenter()
    {
        return center;
    }

    public int GetLength()
    {
        return 2 * radius;
    }

    public int GetRight()
    {
        return center + radius;
    }

    public int GetLeft()
    {
        return center - radius;
    }

    public void Expand()
    {
        ++radius;
    }

    public bool LargerThan(Palindrome other)
    {
        if (other == null)
            return false;

        return (radius > other.radius);
    }

}

private static string GetFormatted(string original)
{
    if (original == null)
        return null;
    else if (original.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder("#");
    foreach (char c in original)
    {
        builder.Append(c);
        builder.Append('#');
    }

    return builder.ToString();
}

private static string GetUnFormatted(string formatted)
{
    if (formatted == null)
        return null;
    else if (formatted.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder();
    foreach (char c in formatted)
    {
        if (c != '#')
            builder.Append(c);
    }

    return builder.ToString();
}

public static string FindLargestPalindrome(string str)
{
    string formatted = GetFormatted(str);

    if (formatted == null || formatted.Length == 0)
        return formatted;

    int[] radius = new int[formatted.Length];

    try
    {
        Palindrome current = new Palindrome(0, 0);
        for (int i = 0; i < formatted.Length; ++i)
        {
            radius[i] = (current.GetRight() > i) ?
                Math.Min(current.GetRight() - i, radius[current.GetMirror(i)]) : 0;

            current = new Palindrome(i, radius[i]);

            while (current.GetLeft() - 1 >= 0 && current.GetRight() + 1 < formatted.Length &&
                formatted[current.GetLeft() - 1] == formatted[current.GetRight() + 1])
            {
                current.Expand();
                ++radius[i];
            }
        }

        Palindrome largest = new Palindrome(0, 0);
        for (int i = 0; i < radius.Length; ++i)
        {
            current = new Palindrome(i, radius[i]);
            if (current.LargerThan(largest))
                largest = current;
        }

        return GetUnFormatted(formatted.Substring(largest.GetLeft(), largest.GetLength()));
    }
    catch (Exception ex) 
    {
        Console.WriteLine(ex);
    }

    return null;
}

using namespace std;

class Palindrome{
public:
    Palindrome(string st){
        s = st; 
        longest = 0; 
        maxDist = 0;
        //ascii: 126(~) - 32 (space) = 94 
        // for 'a' to 'z': vector<vector<int>> v(26,vector<int>(0)); 
        vector<vector<int>> v(94,vector<int>(0)); //all ascii 
        mDist.clear();
        vPos = v; 
        bDebug = true;
    };

    string s;
    string sPrev;    //previous char
    int longest;     //longest palindrome size
    string sLongest; //longest palindrome found so far
    int maxDist;     //max distance been checked 
    bool bDebug;

    void findLongestPal();
    int checkIfAnchor(int iChar, int &i);
    void checkDist(int iChar, int i);

    //store char positions in s pos[0] : 'a'... pos[25] : 'z' 
    //       0123456
    // i.e. "axzebca" vPos[0][0]=0  (1st. position of 'a'), vPos[0][1]=6 (2nd pos. of 'a'), 
    //                vPos[25][0]=2 (1st. pos. of 'z').  
    vector<vector<int>> vPos;

    //<anchor,distance to check> 
    //   i.e.  abccba  anchor = 3: position of 2nd 'c', dist = 3 
    //   looking if next char has a dist. of 3 from previous one 
    //   i.e.  abcxcba anchor = 4: position of 2nd 'c', dist = 4 
    map<int,int> mDist;
};

//check if current char can be an anchor, if so return next distance to check (3 or 4)
// i.e. "abcdc" 2nd 'c' is anchor for sub-palindrome "cdc" distance = 4 if next char is 'b'
//      "abcdd: 2nd 'd' is anchor for sub-palindrome "dd"  distance = 3 if next char is 'c'
int Palindrome::checkIfAnchor(int iChar, int &i){
    if (bDebug)
          cout<<"checkIfAnchor. i:"<<i<<" iChar:"<<iChar<<endl;
    int n = s.size();
    int iDist = 3;
    int iSize = vPos[iChar].size();
    //if empty or distance to closest same char > 2
    if ( iSize == 0 || vPos[iChar][iSize - 1] < (i - 2)){
        if (bDebug)
              cout<<"       .This cannot be an anchor! i:"<<i<<" : iChar:"<<iChar<<endl; 
        //store char position
        vPos[iChar].push_back(i);
        return -1; 
    }

    //store char position of anchor for case "cdc"
    vPos[iChar].push_back(i);    
    if (vPos[iChar][iSize - 1] == (i - 2))
        iDist = 4;
    //for case "dd" check if there are more repeated chars
    else {
        int iRepeated = 0;
        while ((i+1) < n && s[i+1] == s[i]){
            i++;
            iRepeated++;
            iDist++; 
            //store char position
            vPos[iChar].push_back(i);
        }
    }

    if (bDebug)
          cout<<"       .iDist:"<<iDist<<" i:"<<i<<endl; 

    return iDist;
};

//check distance from previous same char, and update sLongest
void Palindrome::checkDist(int iChar, int i){
    if (bDebug)
            cout<<"CheckDist. i:"<<i<<" iChar:"<<iChar<<endl;
    int iDist;
    int iSize = vPos[iChar].size();
    bool b1stOrLastCharInString; 
    bool bDiffDist;

    //checkAnchor will add this char position 
    if ( iSize == 0){
        if (bDebug)
            cout<<"       .1st time we see this char. Assign it INT_MAX Dist"<<endl; 
        iDist = INT_MAX;
    }
    else {
        iDist = i - vPos[iChar][iSize - 1]; 
    }

    //check for distances being check, update them if found or calculate lengths if not.
    if (mDist.size() == 0) {
        if (bDebug)
             cout<<"       .no distances to check are registered, yet"<<endl;
        return;
    }

    int i2ndMaxDist = 0;
    for(auto it = mDist.begin(); it != mDist.end();){
        if (bDebug)
                cout<<"       .mDist. anchor:"<<it->first<<" . dist:"<<it->second<<endl; 
        b1stOrLastCharInString = false; 
        bDiffDist = it->second == iDist;  //check here, because it can be updated in 1st. if
        if (bDiffDist){
            if (bDebug)
                cout<<"       .Distance checked! :"<<iDist<<endl;
            //check if it's the first char in the string
            if (vPos[iChar][iSize - 1] == 0 || i == (s.size() - 1))
                b1stOrLastCharInString = true;
            //we will continue checking for more...
            else {
                it->second += 2; //update next distance to check
                if (it->second > maxDist) {
                     if (bDebug)
                          cout<<"       .previous MaxDist:"<<maxDist<<endl;
                     maxDist = it->second;
                     if (bDebug)
                          cout<<"       .new MaxDist:"<<maxDist<<endl;
                }
                else if (it->second > i2ndMaxDist) {//check this...hmtest
                     i2ndMaxDist = it->second;
                     if (bDebug)
                          cout<<"       .second MaxDist:"<<i2ndMaxDist<<endl;
                }
                it++; 
            }
        }
        if (!bDiffDist || b1stOrLastCharInString) {
            if (bDebug && it->second != iDist)
                cout<<"       .Dist diff. Anchor:"<<it->first<<" dist:"<<it->second<<" iDist:"<<iDist<<endl;
            else if (bDebug) 
                cout<<"       .Palindrome found at the beggining or end of the string"<<endl;

            //if we find a closest same char.
            if (!b1stOrLastCharInString && it->second > iDist){
                if (iSize > 1) {
                   if (bDebug)
                       cout<<"       . < Dist . looking further..."<<endl; 
                   iSize--;  
                   iDist = i - vPos[iChar][iSize - 1];
                   continue;    
                }
            }
            if (iDist == maxDist) {
                maxDist = 0;
                if (bDebug)
                     cout<<"       .Diff. clearing Max Dist"<<endl;
            }
            else if (iDist == i2ndMaxDist) {
                i2ndMaxDist = 0;
                if (bDebug)
                      cout<<"       .clearing 2nd Max Dist"<<endl; 
            }

            int iStart; 
            int iCurrLength;
            //first char in string
            if ( b1stOrLastCharInString && vPos[iChar].size() > 0 && vPos[iChar][iSize - 1] == 0){
                iStart = 0;
                iCurrLength = i+1;
            }
            //last char in string
            else if (b1stOrLastCharInString && i == (s.size() - 1)){
                iStart = i - it->second; 
                iCurrLength = it->second + 1;
            }
            else {
                iStart = i - it->second + 1; 
                iCurrLength = it->second - 1;  //"xabay" anchor:2nd. 'a'. Dist from 'y' to 'x':4. length 'aba':3
            }

            if (iCurrLength > longest){
                if (bDebug)
                      cout<<"       .previous Longest!:"<<sLongest<<" length:"<<longest<<endl;
                longest = iCurrLength;               
                sLongest = s.substr(iStart, iCurrLength);

                if (bDebug)
                      cout<<"       .new Longest!:"<<sLongest<<" length:"<<longest<<endl;
            }

            if (bDebug)
                  cout<<"       .deleting iterator for anchor:"<<it->first<<" dist:"<<it->second<<endl; 

            mDist.erase(it++);
        }
    }


    //check if we need to get new max distance
    if (maxDist == 0 && mDist.size() > 0){ 
        if (bDebug)
              cout<<"       .new maxDist needed";
        if (i2ndMaxDist > 0) {
            maxDist = i2ndMaxDist;
            if (bDebug)
              cout<<"       .assigned 2nd. max Dist to max Dist"<<endl;
        }
        else {
            for(auto it = mDist.begin(); it != mDist.end(); it++){
                if (it->second > maxDist)
                    maxDist = it->second;
            }
            if (bDebug)
              cout<<"       .new max dist assigned:"<<maxDist<<endl;
        }
    }  
};        

void Palindrome::findLongestPal(){
    int n = s.length(); 
    if (bDebug){
        cout<<"01234567891123456789212345"<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl<<endl;            
        for (int i = 0; i < n;i++){
            if (i%10 == 0)
                cout<<i/10;
            else
                cout<<i;
        }
        cout<<endl<<s<<endl;
    }
    if (n == 0)
        return;

    //process 1st char
    int j = 0;
    //for 'a' to 'z' : while (j < n && (s[j] < 'a' && s[j] > 'z'))
    while (j < n && (s[j] < ' ' && s[j] > '~'))
        j++;
    if (j > 0){
        s.substr(j);
        n = s.length();
    }
    // for 'a' to 'z' change size of vector from 94 to 26 : int iChar = s[0] - 'a';
    int iChar = s[0] - ' ';
    //store char position
    vPos[iChar].push_back(0);  

    for (int i = 1; i < n; i++){
        if (bDebug)
            cout<<"findLongestPal. i:"<<i<<" "<<s.substr(0,i+1)<<endl; 
        //if max. possible palindrome would be smaller or equal 
        //             than largest palindrome found then exit
        //   (n - i) = string length to check 
        //   maxDist: max distance to check from i 
        int iPossibleLongestSize = maxDist + (2 * (n - i));
        if ( iPossibleLongestSize <= longest){
            if (bDebug)
                cout<<"       .PosSize:"<<iPossibleLongestSize<<" longest found:"<<iPossibleLongestSize<<endl;
            return;
        }

        //for 'a' to 'z' : int iChar = s[i] - 'a';
        int iChar = s[i] - ' ';
        //for 'a' to 'z': if (iChar < 0 || iChar > 25){
        if (iChar < 0 || iChar > 94){
            if (bDebug)
                cout<<"       . i:"<<i<<" iChar:"<<s[i]<<" skipped!"<<endl;
            continue;
        }

        //check distance to previous char, if exist
        checkDist(iChar, i);

        //check if this can be an anchor
        int iDist = checkIfAnchor(iChar,i);
        if (iDist == -1) 
            continue;

        //append distance to check for next char.
        if (bDebug)
                cout<<"       . Adding anchor for i:"<<i<<" dist:"<<iDist<<endl;
        mDist.insert(make_pair(i,iDist));

        //check if this is the only palindrome, at the end
        //i.e. "......baa" or "....baca" 
        if (i == (s.length() - 1) && s.length() > (iDist - 2)){
            //if this is the longest palindrome! 
            if (longest < (iDist - 1)){
                sLongest = s.substr((i - iDist + 2),(iDist - 1));
            }
        }
    }
};

int main(){
    string s;
    cin >> s;

    Palindrome p(s);
    p.findLongestPal();
    cout<<p.sLongest; 
    return 0;
}




palindrome